# 描述

Lele now is thinking about a simple function $f(x)$.

And $a_i(0<=i<=9)$ can only be 0 or 1 .

Now, I will give $a_0 ~ a_9$ and two positive integers $k$ and $m$ ,and could you help Lele to caculate $f(k)%m$.

## Input

The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers $k$ and $m$. $( k<2*10^9 , m < 10^5 )$
In the second line , there are ten integers represent $a_0 ~ a_9$.

## Output

For each case, output $f(k) % m$ in one line.

• intput

• output

# 思路

• O(n)肯定会T，可以考虑矩阵快速幂求解。
• 由于题目给了递推式，所以很显然我们需要求一个$X$矩阵，使得这个矩阵满足
$\begin{equation*} X^{n - 9} \begin{bmatrix} 9\\ 8\\ 7\\ 6\\ 5\\ 4\\ 3\\ 2\\ 1\\ 0 \end{bmatrix}= X \begin{bmatrix} F(n-1))\\ F(n-2)\\ F(n-3)\\ F(n-4)\\ F(n-5)\\ F(n-6)\\ F(n-7)\\ F(n-8)\\ F(n-9)\\ F(n-10) \end{bmatrix}= \begin{bmatrix} F(n)\\ F(n-1))\\ F(n-2)\\ F(n-3)\\ F(n-4)\\ F(n-5)\\ F(n-6)\\ F(n-7)\\ F(n-8)\\ F(n-9) \end{bmatrix} \end{equation*}$，易得$X=\begin{bmatrix} a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ 1 & 0&0&0&0&0&0&0&0&0\\ 0 & 1&0&0&0&0&0&0&0&0\\ 0 & 0&1&0&0&0&0&0&0&0\\ 0 & 0&0&1&0&0&0&0&0&0\\ 0 & 0&0&0&1&0&0&0&0&0\\ 0 & 0&0&0&0&1&0&0&0&0\\ 0 & 0&0&0&0&0&1&0&0&0\\ 0 & 0&0&0&0&0&0&1&0&0\\ 0 & 0&0&0&0&0&0&0&1&0\\ \end{bmatrix}$
将$F_{n}$按递推式展开，取对应系数即可，
• 递推式是从10开始的，所以对与第$n$项，只需求$X^{n-9}$，所得矩阵再左乘一个$\begin{bmatrix}F_9 & F_8 & F_7 & F_6 & F_5 & F_4& F_3& F_2& F_1& F_0\end{bmatrix}^{-1}$，所得矩阵的第一个元素即为$F_i$

# 代码

-------------本文结束 感谢您的阅读-------------