TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3712
  • Problem
  • P3712数列
    Limits : Time Limit : - MS   Memory Limit : 65536 KB
    Judgment Tips : 时限1000ms
    Description

    a[1]=a[2]=a[3]=1

    a[x]=a[x-3]+a[x-1]  (x>3)

    求a数列的第n项对1000000007(10^9+7)取余的值。

    Input Format

    第一行一个整数T,表示询问个数。

    以下T行,每行一个正整数n。

    Output Format

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

    Sample Input

    3
    6
    8
    10

    Sample Output

    4
    9
    19

    Hint

    对于30%的数据 n<=100;

    对于60%的数据 n<=2*10^7;

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