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

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

对于 $100\%$ 的数据 $1 \leq T \leq 100$，$1 \leq n \leq 2 \times 10^9$。