1470. 刻晴的每日精进

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

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

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

输入

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

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

输出

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

样例

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

来源

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

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