DGAME  Game
Digo is planning to recruit members for his ACM team, he designs a game in which who ever beats him will be recruited in his team. Darshil is a friend of yours. You have to help him get recruited in Digo's ACM team.
There are N piles , where i^{th} pile contains either 2*i or 2*i+1 stones. During the game, Darshil and Digo take turns and Darshil takes the first turn. In each turn they can select any pile containing 2 or more stones and then remove an EVEN number of stones from the selected pile. The player who can't make the next move loses the game.
You have to find:
1. Number of ways in which stones can be put in those N piles. (Each way is distinct if any one pile has different number of stones). If number of ways is M then print M % 1000000007.
2. For each configuration of part1 Darshil counted the number of ways he can choose the first move such that no matter how optimally Digo plays he wins. Find the integral part of average number of such ways of all the configurations.
Input Format
The first line contains an integer T (number of test cases).
Each of the next T lines contains a single positive integer N.
Output Format
T lines containing two spaceseparated integers  the answers to the first and second parts of the questions.
Constraints
1 <= N <= 10^9
1 <= T <= 10^3
Sample Input
3
1
2
3
Sample Output
2 1
4 1
8 0
hide comments
Vamsi Krishna Avula:
20141228 13:01:47
good question :) 

Mitch Schwartz:
20130914 03:10:24
@Ivan Hendrajaya: Please choose one account and disqualify AC submissions from the other. Submitting with multiple accounts dilutes points for nothing. Last edit: 20130914 04:22:27 
Added by:  Surya Kiran 
Date:  20130905 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Codeblitz4 