题目描述
定义字符串序列 $F_1,F_2,\ldots$ 如下：
$$ F_1=dt,\\ F_{k+1}=F_kF_kt $$
计算 $F_n$ 有多少个本质不同的子序列，对 $10^9+7$ 取模。
输入格式
第一行一个整数 $T(1\leq T\leq 10)$ ，表示数据组数。
接下来 $T$ 行，每行一个正整数 $n(1\leq n\leq 10^{18})$ ，表示一组数据。
输出格式
一行 $T$ 个整数，表示答案。
样例输入
4 1 2 3 100000
样例输出
4 17 226 73460621
样例解释
$F_1=\text{dt},F_2=\text{dtdtt},F_3=\text{dtdttdtdttt}$ 。
数据范围
保证 $1\leq T\leq 10,1\leq n\leq 10^{18}$
subtask1(24pts)：保证 $n\leq 18$ 。
subtask2(12pts)：保证 $n\leq 2000$ 。
subtask3(15pts)：保证 $n\leq 10^6$ 。
subtask4(11pts)：保证 $n\leq 10^9$ 。
subtask5(38pts)：无特殊限制。