시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 2 2 2 100.000%

문제

Consider the sequence of strings F1, F2, . . . , defined as:

F1 = ab,

Fk+1 = FkFkb.

Calculate the number of distinct subsequences of the string Fn modulo 109 + 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 ≤ 1018), 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.

예제 입력 1

3
1 2 3

예제 출력 1

4 17 226

힌트

The first three strings are: F1 = ab, F2 = ababb, and F3 = ababbababbb.