Key Set

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1476    Accepted Submission(s): 726

Problem Description

soda has a set 

S with n integers {

1,2,…,n}. A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S are key set.

 

 

Input

There are multiple test cases. The first line of input contains an integer 

T (1≤T≤105), indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤109), the number of integers in the set.

 

 

Output

For each test case, output the number of key sets modulo 1000000007.

 

 

Sample Input

4 1 2 3 4

 

 

Sample Output

0 1 3 7

 

1 #include 
       
         2 #include 
        
          3 using namespace std; 4 long long mod=1000000007; 5  6 long long pow_mod(long long x, long long n)    { 7     long long res = 1; 8     while (n)    { 9         if (n & 1)    res = res * x % mod;10         x = x * x % mod;11         n >>= 1;12     }13     return res;14 }15 16 int main()17 {18     int T;19     long long n;20     scanf("%d",&T);21     while(T--)22     {23         scanf("%I64d",&n);24         printf ("%I64d\n", pow_mod (2, n - 1) - 1);25     }26     return 0;27 }