P4838 Brother P Cracks the Password

Brother P is a boy who often loses his password slips. At the ION8102 contest site, Brother P lost his password slip again. As someone who can get full marks on the written test, he of course knows that this will cost him $5$ points as a penalty, so he started cracking the password of the IONXunil system.

Define a string as valid if and only if it is made up only of $\verb!A!$ and $\verb!B!$, and it does not contain $3$ consecutive $\verb!A!$ characters. Brother P knows that the password is the number of valid strings of length $N$, taken modulo $19260817$. But Brother P cannot compute it, so he can only tell you $N$ and ask you to compute it. As for why the result is taken modulo this number, it seems to be in memory of someone, but who exactly that is, Brother P does not remember either. However, he forgot what the string length $N$ should be, so he plans to try $M$ sets of testdata.

The first line gives an integer $M$, which represents the number of queries. Then follow $M$ lines, each giving a positive integer $N$, meaning the length of the string in that query.

For each query, output one integer per line, representing the answer.

### Explanation of the samples. When the length is $1$, there are only two arrangements: $\verb!A!$ and $\verb!B!$, and both are valid. When the length is $3$, all strings are valid except $\verb!AAA!$, so there are $2^3-1$ strings. ### Constraints. - For $20\%$ of the testdata, all $N\leq20$, $M\leq2$. - For $70\%$ of the testdata, all $N\leq10^7$. - For $100\%$ of the testdata, all $N\leq10^9$, $M\leq10$. Translated by ChatGPT 5