P3712数列 | ||
|
问题描述
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007(10^9+7)取余的值。
输入格式
第一行一个整数T,表示询问个数。
以下T行,每行一个正整数n。
输出格式
每行输出一个非负整数表示答案。
样例输入
3
6
8
10
样例输出
4
9
19
提示
对于30%的数据 n<=100;
对于60%的数据 n<=2*10^7;
对于100%的数据 T<=100,n<=2*10^9;