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 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⁹+7

Input

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

The next T lines will contain 1 ≤ K ≤ 10⁷, 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