P1939 矩阵加速（数列）
题目描述
已知一个数列 $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$ 取余的值。
输入格式
无
输出格式
无
说明/提示
- 对于 $30\%$ 的数据 $n \leq 100$；
- 对于 $60\%$ 的数据 $n \leq2 \times 10^7$；
- 对于 $100\%$ 的数据 $1 \leq T \leq 100$，$1 \leq n \leq 2 \times 10^9$。