该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+ax-1
求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；