【模板】矩阵加速(数列)

题目描述

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。

输出格式


每行输出一个非负整数表示答案。

输入输出样例

输入样例 #1

3
6
8
10

输出样例 #1

4
9
19

说明

对于30%的数据 n<=100; 对于60%的数据 n<=2\*10^7; 对于100%的数据 T<=100,n<=2\*10^9;