ZZY是一个善于思考的农民。有一天，他在放牛时想到了一个问题：
当前ZZY有n(3<=n<=1000)头牛，排成一列（牛的编号只能从1，2，3……n中选择，编号可以重复），现在他想把牛编号，编号规则是：第i头牛的编号必须小于第i+2和第i+3头牛的编号，编号可以重复。（如果第i+2头牛不存在，则第i头牛就可以不被i+2这个条件约束，i+3不存在也一样）。能有多少种编号方法。
突然间他发现自己被自己的问题难倒了，相信聪明的你能帮他解决这个问题（由于答案过大，输出对M=1000007取模）。

先输入一个T，表示有T个输入：
第2至T+1行每行输入一个n，表示有n头牛排成一列。

编号方法有多少种，每个答案一行。

9种方法分别为: (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3), (2,1,3), (2,2,3), (2,3,3).

浙江师范大学数理与信息工程学院第三届新生C语言程序设计竞赛