18612번 - Magic Strings 다국어

문제

Consider the sequence of strings F₁, F₂, . . . , defined as:

F₁ = ab,

F_k+1 = F_kF_kb.

Calculate the number of distinct subsequences of the string F_n modulo 10⁹ + 7.

입력

The first line of input contains a single integer t (1 ≤ t ≤ 10), which is the number of test cases.

The second line of input contains t integers n (1 ≤ n ≤ 10¹⁸), one for each test case.

출력

For each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces.

제한

힌트

The first three strings are: F₁ = ab, F₂ = ababb, and F₃ = ababbababbb.