Exam time

All submissions for this problem are available.
Suppose a few students are giving an exam in the examination hall.The supervisor is bored of keeping a watch on the students so as they don't
copy. However being a programmer, she has noticed few things.
The examination hall is a 2D grid with M rows and N seats in each row. However students in say ,row 1 are the most mischievous
and copy the most,But they don't copy from students of other rows as they are afraid of being caught. The N students seated in row
1 are numbered from 1 to N.
Also a student in a single row of N seats can only copy from a student sitting either just ahead of him or just behind him .For 1st
and last student in the row, they can only copy only from 2nd and 2nd to last student respectively.
Now the supervisor gets bored and starts thinking about how many ways can we select a nonempty subset of those N students in 1st row
such that :
For each of those selected subsets:
(a)There are no two students who can copy from each other.
(b)Addition of any of the remaining students in this subset results in copying.
Note : Remaining students for a subset means students from 1 to N who are not present in this subset
As answers can be large, print it modulo 1000000007(1e9+7).
Sample Explanation :
For N=5,there are 4 valid subsets = ({1,4},{2,4},{1,3,5},{2,5})
Subset {2,5} is valid subset because :
1) Student 2 and student 5 can't copy. So it satisfies property (a)
2) if we add student 1, then student 1 and student 2 will copy
if we add student 3, then student 2 and student 3 will copy
if we add student 4, then student 4 and student 5 will copy
Hence we cant add any of remaining students to this subset.So it satisfies property (b)
Similarly {1,4} , {2,4} , {1,3,5} are valid subsets.
Subset {1,5} is not valid because :
if we add student 3 in this subset ,still no one can copy.Hence,it doesn't satisfy property (b).
Subset {1,2,5} is not valid because :
Student 1 and student 2 can copy. Hence,it doesn't satisfy property (a).
Similarly the remaining 25 subsets for N=5 are invalid.
Thus ,for N=5 , valid subsets(output) = 4
Input
First line will be number of test cases T.
Each test case will have a single number N.
Output
Number of subsets which satisfy both property (a) and (b) in a single line for each test case
Constraints
1<=T<=10^5
1<=N<=10^6
Example
4 1 2 5 30 Output: 1 2 4 4410
Author:  dhaval242 
Tags  dhaval242 
Date Added:  18022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions