题目描述

定义字符串序列 $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)：无特殊限制。