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 binary-vectors of length K, he can generate an infinitely long binary vector, which will have none of the smaller vectors as substring. Ada claimed opposite and now she is preparing 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 2K 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 realized 2K 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 109+7

Input

The first line of input will contain 1 ≤ T ≤ 106, the number of test-cases.

The next T lines will contain 1 ≤ K ≤ 107, the size of binary vectors Ada wants to generate.

Output

For each test-case, 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

Added by:Morass
Date:2017-12-19
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-07-20 14:52:53
咋写这题
2021-04-16 23:56:55 Scape
Why so many input files? Just one should have been good enough.
2017-12-20 01:00:32
Hope it is OK as you've succesfully made it through :D
2017-12-19 20:28:26
+1
2017-12-19 19:41:27
Don't remove the problem please :P even if it is wrong
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.