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 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 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 realzed 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
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.
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.
7 1 2 3 13 666 123456 3141592
2 3 4 632 595842408 994717838 244191463
Examples of first 3 inputs:
0,1 00,01,11 000,001,101,111
Hope it is OK as you've succesfully made it through :D
Don't remove the problem please :P even if it is wrong