#2198. 贴贴序列

贴贴序列

贴贴序列

题目描述

标题: 贴贴序列 - Problem - QOJ.ac

#8367. 贴贴序列

Statistics

The problem was used in the following contests:

题目描述

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
1 2 3 100000
4 17 226 73460621