P4838 P哥破解密码

P 哥是一个经常丢密码条的男孩子。 在 ION8102 赛场上，P 哥又弄丢了密码条，笔试满分的他当然知道这可是要扣 $5$ 分作为惩罚的，于是他开始破解 IONXunil 系统的密码。

定义一个串合法，当且仅当串只由 $\verb!A!$ 和 $\verb!B!$ 构成，且没有连续的 $3$ 个 $\verb!A!$。P 哥知道，密码就是长度为 $N$ 的合法字符串数量对 $19260817$ 取模的结果。但是 P 哥不会算，所以他只能把 $N$ 告诉你，让你来算。 至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P 哥也不记得了。 然而他忘记字符串长度 $N$ 应该是多少了，于是他准备试 $M$ 组数据。

无

无

### 样例部分解释 :。 长度为 $1$ 时只有 $\verb!A!$ 和 $\verb!B!$ 两种排列，都是合法的。 长度为 $3$ 时除了 $\verb!AAA!$ 是不合法的其他都是可以的，故有 $2^3-1$ 种。 ### 数据范围。 - 对于 $20\%$ 数据，全部 $N\leq20$，$M\leq2$； - 对于 $70\%$ 数据，全部 $N\leq10^7$； - 对于 $100\%$ 数据，全部 $N\leq10^9$，$M\leq10$。