시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 6 | 4 | 4 | 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.
3 1 2 3
4 17 226
The first three strings are: F1 = ab
, F2 = ababb
, and F3 = ababbababbb
.