Problem Description

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

Input Format

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 Format

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

1000
3
3 2 1

110

11111100101
4
2 0 2 1

143901603

1001011001101001
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

184740992

Hint

For all test points: $0\le \log_2n<5\times 10^5$, $1\le k\le 500$, $0\le a_i < 10^9 + 7$, $a_{k-1}\ne 0$.

Thanks to s_r_f for providing the testdata.

Translated by ChatGPT 5