QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100

# 8367. 贴贴序列

Statistics

题目描述

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