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
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
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
2016-06-22 20:29:25
@Piyush: My programs gives correct output for test cases and other manual test cases. Can you please check my submission and give some test cases where it fails. My ideone submission is http://ideone.com/**********
Someone please check. Thanks

=(Francky)=> Use forum for links to code ; it's the place for that. Psetter can see your code in any case ; no need to give a link.

Last edit: 2016-06-22 20:44:06
2016-06-22 16:13:56 Bhuvnesh Jain
Are the given sample test cases correct? I think the answer for n = 4 should be 100 instead of 110.

Re: The sample test cases are correct!

EDIT: Nice question. Interpreted it wrongly initially.

Last edit: 2016-06-22 22:29:02
2016-06-21 12:43:41 Siddharth Singh
As Soon As I Saw The Inputs I Knew I Had Solved This One ;)
Had To Rip My Ass Off To Get The Formula
Piece Of CAKE Now .
Pure SAVAGE
2016-06-21 10:13:56 Francky
In input file, last line isn't feed with "\n".
Why merge ranklist with a single language per user ? It's quite unusual.

Re: Have made the requisite changes!

=(Francky)=> Thanks for that.

Last edit: 2016-06-21 12:33:21
2016-06-21 00:46:18
time limit too strict, even the fastest algo possible does not work

Re: I beg to differ. Decent code even in slower languages can pass. Make some optimizations in your code.

Last edit: 2016-06-21 03:31:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.