Coding is the closest thing we have to superpower ！
描述
已知一个数列 a，它满足：
a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases}
求 a 数列的第 n 项对 10^9+7 取余的值。
输入
第一行一个整数 T，表示询问个数。
以下 T 行，每行一个正整数 n。
- 对于 30\% 的数据 n \leq 100；
- 对于 60\% 的数据 n \leq2 \times 10^7；
- 对于 100\% 的数据 1 \leq T \leq 100，1 \leq n \leq 2 \times 10^9。
输出
每行输出一个非负整数表示答案。
样例
输入
3 6 8 10
输出
4 9 19
标签