VECTAR5  Count Subsets
You are given a set S = {1, 2, 3, ..., n}. Your task is simple. You have to calculate the number of ways of selecting non empty subsets A and B such that A is not a subset of B and B is not a subset of A. Since answer can be large output the result mod 10^9 + 7.
Input
First line of input contains single integer t denoting number of test cases.
Next t lines contain a single integer n.
Output
For each test case output answer to problem by taking mod with 10^9 + 7.
Constraints
1 <= t <= 100000
1 <= n <= 1000000
Example
SAMPLE INPUT: 2 4 8 SAMPLE OUTPUT: 110 52670
hide comments
ASHUTOSH DWIVEDI:
20160816 12:15:01
@Piyush i think this is same as hackerearth candy distribution 3 problem it should be mentioned in the resource.


vaibhav138:
20160720 18:56:20
Took a while to get the formula :) 

manish kumar:
20160630 10:05:26
please look at my solution i don't know why i am getting tle


citransvostok:
20160626 14:27:18
FInding out solution is easy, watch out for negatives Last edit: 20160626 14:28:51 

wano:
20160625 15:30:19
Please have a look at my Python solution.


kartiks025:
20160623 19:53:05
@Piyush can you check why I'm getting wrong answer because according to me it should be correct


Shubham Dash:
20160623 19:05:02
@VIpul: Can you explain how the answer came out to be 18 for n=3? 

Vipul Srivastava:
20160623 17:16:32
Is the output 18 for input 3?


aqua_regia:
20160623 12:04:14
I see it, problem with modular subtraction. What should be done instead?


aqua_regia:
20160622 23:03:00
@Francky: okey then this is the link to forum. http://discuss.spoj.com/t/waincountsubsetsvectar5/15298

Added by:  Piyush Kumar 
Date:  20160620 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 