P1939 Matrix Exponentiation (Sequence)

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$.

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

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

- 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