VECTAR5 - Count Subsets

no tags 

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
evang12: 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)

joe85123: 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.

ASHUTOSH DWIVEDI: 2016-08-16 12:15:01

@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
vaibhav138: 2016-07-20 18:56:20

Took a while to get the formula :)

manish kumar: 2016-06-30 10:05:26

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
citransvostok: 2016-06-26 14:27:18

FInding out solution is easy, watch out for negatives

Last edit: 2016-06-26 14:28:51
wano: 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
kartiks025: 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
Shubham Dash: 2016-06-23 19:05:02

@VIpul: Can you explain how the answer came out to be 18 for n=3?

Vipul Srivastava: 2016-06-23 17:16:32

Is the output 18 for input 3?

Re: Yes.

Last edit: 2016-06-23 17:48:23

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