1470. 刻晴的每日精进

“日复一日,必有精进”是刻晴的座右铭,所以她每天都根据前三天自己的学习情况来提高自己。

设刻晴 f(i)f(i) 为刻晴第 ii 天的学习情况,且 f(1)=1,f(2)=1,f(3)=1f(1)=1,f(2)=1,f(3)=1 ,则 f(i)=2f(i1)+f(i2)f(i3)i>3f(i)=2*f(i-1)+f(i-2)-f(i-3),i>3

求刻晴第 ii 天的学习情况。

输入

输入 nn ,表示有 nn 个询问 (1n1000)(1 \leq n \leq 1000)

之后一行有 nn 个以空格间隔的数: a1,a2,...,ana_1,a_2,...,a_n ,表示 nn 个询问 (1ai1012)( 1 \leq a_i \leq 10^{12} )

输出

对于每个询问,每行输出对应的 f(ai)f(a_i) ,答案对 10000000071000000007 取模

样例

标准输入 复制文本
2
1 5
标准输出 复制文本
1
4

来源

2021 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 332
通过 93