#P16153. [2022国家队训练南京站]贴贴序列

[2022国家队训练南京站]贴贴序列

题目描述

定义字符串序列 F1,F2,…F_1,F_2,\ldots 如下:

F1=dt,Fk+1=FkFktF_1=dt,\qquad F_{k+1}=F_kF_kt

计算 FnF_n 有多少个本质不同的子序列,对 109+710^9+7 取模。

输入格式

第一行一个整数 T (1≤T≤10)T\ (1\le T\le 10),表示数据组数。

接下来 TT 行,每行一个正整数 n (1≤n≤1018)n\ (1\le n\le 10^{18}),表示一组数据。

输出格式

一行 TT 个整数,表示答案。

样例

样例输入

4
1 2 3 100000

样例输出

4 17 226 73460621

样例解释

F1=dtF_1=\text{dt},F2=dtdttF_2=\text{dtdtt},F3=dtdttdtdtttF_3=\text{dtdttdtdttt}。

数据范围

保证 1≤T≤101\le T\le 10,1≤n≤10181\le n\le 10^{18}。

子任务 分值 限制
Subtask 1 24 pts 保证 n≤18n\le 18
Subtask 2 12 pts 保证 n≤2000n\le 2000
Subtask 3 15 pts 保证 n≤106n\le 10^6
Subtask 4 11 pts 保证 n≤109n\le 10^9
Subtask 5 38 pts 无特殊限制