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

Added by:Piyush Kumar
Date:2016-06-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2022-01-06 03:04:18
There's a formula to this problem? I only found a DP solution :(

Can someone tell me the formula? (Closed formula, of course)
2020-01-17 17:06:22
Very nice problem. Took a while to come up with the formula. It turned out to be a simple and elegant one.
2016-08-16 12:15:01 ASHUTOSH DWIVEDI
@Piyush i think this is same as hackerearth candy distribution 3 problem it should be mentioned in the resource.

Re: I came across this as a math problem somewhere else, so I don't know if I should put it on resource.

Last edit: 2016-08-17 12:33:47
2016-07-20 18:56:20
Took a while to get the formula :)
2016-06-30 10:05:26 manish kumar
please look at my solution i don't know why i am getting tle

Re: Your approach is wrong.

Last edit: 2016-06-30 11:29:48
2016-06-26 14:27:18
FInding out solution is easy, watch out for negatives

Last edit: 2016-06-26 14:28:51
2016-06-25 15:30:19
Please have a look at my Python solution.

Re: You are getting TLE because of the exponentiation without mod. Fix that.

Last edit: 2016-06-25 17:39:42
2016-06-23 19:53:05
@Piyush can you check why I'm getting wrong answer because according to me it should be correct

Re: You have issues with modular operations. Check for n=113

Last edit: 2016-06-24 12:01:58
2016-06-23 19:05:02 Shubham Dash
@VIpul: Can you explain how the answer came out to be 18 for n=3?
2016-06-23 17:16:32 Vipul Srivastava
Is the output 18 for input 3?

Re: Yes.

Last edit: 2016-06-23 17:48:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.