#1060. 矩阵加速(数列)

矩阵加速(数列)

题目描述

已知一个数列 aa,它满足:

$$a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases}$$

求 aa 数列的第 nn 项对 109+710^9+7 取余的值。

输入格式

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

以下 TT 行,每行一个正整数 nn。

输出格式

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

样例

3
6
8
10
4
9
19

题目来源:洛谷 P1939