【模板】矩阵加速(数列)

题目描述

已知一个数列 $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$。

输出格式


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

输入输出样例

输入样例 #1

3
6
8
10

输出样例 #1

4
9
19

说明

- 对于 $30\%$ 的数据 $n \leq 100$; - 对于 $60\%$ 的数据 $n \leq2 \times 10^7$; - 对于 $100\%$ 的数据 $1 \leq T \leq 100$,$1 \leq n \leq 2 \times 10^9$。