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
hide comments
|
evang12:
2022-01-06 03:04:18
There's a formula to this problem? I only found a DP solution :(
|
|
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.
|
|
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
|
|
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.
|
|
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
|
|
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?
|
| 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 |
RSS