P7468 [NOI Online 2021 Senior] Angry Little N

The extremely angry Little N played a game to vent his anger. This game has a total of $n$ levels: Level $0$, Level $1$, Level $2$, $\cdots$, Level $n-1$. Some of these levels are normal levels, and the others are bonus levels. The distribution of normal and bonus levels in this game is special. Let character $\texttt{a}$ represent a normal level, and character $\texttt{b}$ represent a bonus level. Then the string formed by Level $0$, Level $1$, Level $2$, $\cdots$, Level $n-1$ in order is a prefix of an infinite string $s$, and $s$ can be constructed as follows: 1. Initially, $s$ is the string containing a single character $\texttt{a}$. 2. Replace every character $\texttt{a}$ in $s$ with $\texttt{b}$, and every character $\texttt{b}$ in $s$ with $\texttt{a}$ to obtain a string $t$, then append $t$ to the end of $s$. 3. Repeat step 2 continuously. The resulting string is the final $s$. We can see that $s=\texttt{abbabaabbaababba}\cdots$. Therefore, Level $0$ of this game is a normal level, Level $1$ is a bonus level, Level $2$ is a bonus level, Level $3$ is a normal level, and so on. Passing Level $i$ gives $f(i)$ points, where $f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}$ is a fixed polynomial of degree $k-1$. When Little N cleared the game in a fit of anger, he passed all bonus levels and ignored all normal levels, and then uninstalled the game. Now, thinking back, he wants to know the result of his total score before uninstalling the game modulo $10^9+7$.

The first line contains a positive integer $n$, which is the number of levels in the game. For convenience, $n$ is given in binary. The second line contains a positive integer $k$, which is one plus the degree of the polynomial. The third line contains $k$ non-negative integers $a_0,a_1,a_2,\cdots,a_{k-1}$, which are the coefficients of the polynomial terms.

Output one line containing a non-negative integer, which is Little N's total score before uninstalling the game modulo $10^9 + 7$.

For all test points: $0\le \log_2n