“日复一日，必有精进”是刻晴的座右铭，所以她每天都根据前三天自己的学习情况来提高自己。
设刻晴 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 |