Description

Given a sequence $a$, it satisfies:

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

Find the $n$-th term of sequence $a$ modulo $10^9+7$.

Input Format

The first line contains an integer $T$, denoting the number of queries. Each of the following $T$ lines contains a positive integer $n$.

Output Format

Output one non-negative integer per line, representing the answer.

3
6
8
10

4
9
19

Hint

• For $30\%$ of the testdata, $n \leq 100$.
• For $60\%$ of the testdata, $n \leq 2 \times 10^7$.
• For $100\%$ of the testdata, $1 \leq T \leq 100$, $1 \leq n \leq 2 \times 10^9$.

Translated by ChatGPT 5