数列
Description
已知一个数列\(a\)，满足：
\(a_1=a_2=a_3=1\)
\(a_i=a_{i-1}+a_{i-3} (i \geq 4)\)
求数列\(a\)第\(n\)项对\(10^9+7\)取余的值
Format
Input
第一行一个整数\(T\)表示询问个数
一下T行每行一个正整数\(n\)
Output
每行输出一个非负整数表示答案
Sample 1
Input
3
6
8
10
Output
4
9
19
Limitation
2s, 256MB for each test case.
对于30%的数据\(n \leq 100 \)
对于100%的数据\( 1 \leq T \leq 100, 1 \leq n \leq 2 \times 10^9\)
