Magic Strings
시간 제한4초메모리 제한512 MB
재귀적으로 정의된 문자열 Fn의 서로 다른 부분수열의 개수를 1e9+7로 나눈 나머지로 구한다. n은 1e18까지 커질 수 있다.
문제
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.
힌트
The first three strings are: F1 = ab, F2 = ababb, and F3 = ababbababbb.