SPOJ.com - Problem VECTAR5

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

Submit solution!

hide comments

< Previous 1 2 Next >

	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
	aqua_regia: 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**
	Bhuvnesh Jain: 2016-06-22 16:13:56 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
	Siddharth Singh: 2016-06-21 12:43:41 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
	Francky: 2016-06-21 10:13:56 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
	meettaraviya: 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

Submit solution!

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