“日复一日,必有精进”是刻晴的座右铭,所以她每天都根据前三天自己的学习情况来提高自己。
设刻晴 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≤n≤1000)
之后一行有 n 个以空格间隔的数: a1,a2,...,an ,表示 n 个询问 (1≤ai≤1012)
输出
对于每个询问,每行输出对应的 f(ai) ,答案对 1000000007 取模
样例
标准输入 复制文本 |
2
1 5
|
标准输出 复制文本 |
1
4
|
来源
2021 软件学院 ACM 集训队筛选赛