ADASETS  Ada and Sets
Ada the Ladybug is attending Assertive Club of Mathematicians. On last session, Ada had a fight with her friend Horntail Hansel. Hansel claimed, that if somebody picks a set of binaryvectors of length K, he can generate an infinetly long binary vector, which will have none of the smaller vectors as substring. Ada claimed opossite and now she is prepairing a proof, she could pick a set (for any K), that every such infinite vector will contain at least one of her vectors as substring. Obviously, it is true, since if she picks all 2^{K} vectors, Hansel's vector will always have at least one of such vectors as substring (and even as prefix).
She also wanted to construct such set, to add to importance, but then she realzed 2^{K} is too much, so instead she wanted to construct minimal such set. Can you help her to find the size of such set? Even though it might be lesser, it is still pretty big, so output it modulo 10^{9}+7
Input
The first line of input will contain 1 ≤ T ≤ 10^{6}, the number of testcases.
The next T lines will contain 1 ≤ K ≤ 10^{7}, the size of binary vectors Ada wants to generate.
Output
For each testcase, output the minimum number of binary vectors of length K Ada has to generate, so that Hansel can't make an infinite vector which wouldn't have at least one of Ada's vectors as substring. Output this modulo 1000000007.
Example Input
7 1 2 3 13 666 123456 3141592
Example Output
2 3 4 632 595842408 994717838 244191463
Examples of first 3 inputs:
0,1 00,01,11 000,001,101,111
hide comments
morass:
20171220 01:00:32
Hope it is OK as you've succesfully made it through :D 

mahmud2690:
20171219 20:28:26
+1 

barishnamazov:
20171219 19:41:27
Don't remove the problem please :P even if it is wrong 
Added by:  Morass 
Date:  20171219 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 