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
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
aqua_regia: 2016-06-23 12:04:14

I see it, problem with modular subtraction. What should be done instead?

Re: The remedy is not too difficult to think of.

Last edit: 2016-06-23 13:59:17
aqua_regia: 2016-06-22 23:03:00

@Francky: okey then this is the link to forum. http://discuss.spoj.com/t/wa-in-count-subsets-vectar5/15298
if you could please check and tell whats wrong. Are there some tricky cases??

Re: I have checked your code. Your code gives negative output to some of the test cases. Find out why!

Last edit: 2016-06-23 06:25:16

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