jqe的数列

题目介绍

jqe 有一个数列 $a$ (下标从 $1$ 开始), 其满足

$$a_i = \begin{cases}
1 & 1 \le i \le 3 \\ a_{i-1} + a_{i-2} + a_{i-3} & i \ge 4 \end{cases}$$

有 $q$ 次询问，每次询问给定一个正整数 $n$，你需要计算 $\sum _{i=1}^n a_i$ 对 $10^9 + 7$ 取模后的值。

输入格式

第一行一个整数 $q$（$1 \leq q \leq 10^5$）。

接下来的 $q$ 行，每行一个整数 $n$（$1 \leq n \leq 10^6$），含义见上。

输出格式

输出 $q$ 行，每行一个整数，表示 $\sum _{i=1}^n a_i$ 对 $10^9 + 7$ 取模后的值。

输入样例

2
4
999999

输出样例

6
675267001

样例解释

$a$ 的前 $4$ 项分别为 $1,1,1,3$ , 所以前 $4$ 项之和为 $6$ 。

HINT

本题需要考虑性能问题。

这道题在 $q$ 较小 ,$ n \le 10^{15}$ 的时候也是可以做的，这里留给有兴趣的同学思考，也欢迎与出题人讨论

AUTHOR：shorn1