QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[0]

# 8367. 贴贴序列

Statistics

题目描述

定义字符串序列 F1,F2, 如下:

F1=dt,Fk+1=FkFkt

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

输入格式

第一行一个整数 T(1T10) ,表示数据组数。

接下来 T 行,每行一个正整数 n(1n1018) ,表示一组数据。

输出格式

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

样例输入

4
1 2 3 100000

样例输出

4 17 226 73460621

样例解释

F1=dt,F2=dtdtt,F3=dtdttdtdttt

数据范围

保证 1T10,1n1018

subtask1(24pts):保证 n18

subtask2(12pts):保证 n2000

subtask3(15pts):保证 n106

subtask4(11pts):保证 n109

subtask5(38pts):无特殊限制。