题目描述
定义字符串序列 F1,F2,… 如下:
F1=dt,Fk+1=FkFkt
计算 Fn 有多少个本质不同的子序列,对 109+7 取模。
输入格式
第一行一个整数 T(1≤T≤10) ,表示数据组数。
接下来 T 行,每行一个正整数 n(1≤n≤1018) ,表示一组数据。
输出格式
一行 T 个整数,表示答案。
样例输入
4 1 2 3 100000
样例输出
4 17 226 73460621
样例解释
F1=dt,F2=dtdtt,F3=dtdttdtdttt 。
数据范围
保证 1≤T≤10,1≤n≤1018
subtask1(24pts):保证 n≤18 。
subtask2(12pts):保证 n≤2000 。
subtask3(15pts):保证 n≤106 。
subtask4(11pts):保证 n≤109 。
subtask5(38pts):无特殊限制。