Count Relations

All submissions for this problem are available.
Let A be a set of the first N positive integers :A={1,2,3,4.........N}
Let B be the set containing all the subsets of A.
Professor Eric is a mathematician who defined two kind of relations R1 and R2 on set B.
The relations are defined as follows:
R1={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is equal to empty set }
R2={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is not equal to empty set }
Now given the number N,Professor Eric wants to know how many relations of kind R1 and R2 exists.Help him.
NOTE : (x,y) is the same as (y,x) ,i.e the pairs are unordered.
Input format:
The first line contains the number of test cases T.Each of the test case is denoted by a single integer N.
Output format:
Output T lines, one for each test case,containing two integers denoting the number of relations of kind R1 and R2 respectively, modulo 100000007.
Example
Sample Input: 3 1 2 3 Sample Output: 0 0 1 0 6 3 Constraints: 1 <= T <= 1000 1 <= N <= 10^18 Explanation: Let A={1,2} Then B={Phi,{1},{2},{1,2}} Phi=Empty Set So R1=Either {({1},{2})} or {({2},{1})} and R2=No relation exists So,there is 1 relation of kind R1 and 0 relation of kind R2.
Author:  nssprogrammer 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/COUNTREL 
Tags  easy jan11 nssprogrammer 
Date Added:  4122010 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CS2, D, GO, JAVA, PAS fpc, PAS gpc 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions