마법 문자열

문자열의 수열 $F_1, F_2, \ldots$ 을 다음과 같이 정의한다.

$F_1 =$ ab

$F_{k+1} = F_k F_k$ b

문자열 $F_n$의 서로 다른 부분 수열의 개수를 $10^9 + 7$로 나눈 나머지를 구하시오.

첫 번째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10$)가 주어진다. 두 번째 줄에는 각 테스트 케이스마다 정수 $n$ ($1 \le n \le 10^{18}$)이 $t$개 주어진다.

각 테스트 케이스에 대해 문제의 답을 정수 하나로 출력한다. 연속된 답은 공백 한 칸으로 구분한다.

처음 세 문자열은 다음과 같다. $F_1$ = ab, $F_2$ = ababb, $F_3$ = ababbababbb.