New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1129: 数列

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：92 通过：22
提交提交记录统计

题目描述

给定一个数列a：
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1]
求第n项值，答案对10^9+7取模

输入格式

第一行一个整数T，表示询问个数。以下T行，每行一个正整数n。
1<=T<=100, 1<=n<=2∗10^9

输出格式

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

输入样例 复制 

3
6
8
10

输出样例 复制 

4
9
19