Problem Description

An extremely angry N clears a game to vent her frustration.

The game has $n$ levels, numbered from $0$ to $n-1$. Some of these levels are normal levels, while others are bonus levels.

The distribution of normal and bonus levels in this game is quite special. If we use the character $\texttt{a}$ to represent a normal level and the character $\texttt{b}$ to represent a bonus level, then the string formed by the levels from $0$ to $n-1$ is a prefix of an infinite string $s$ constructed as follows:

1. Initially, $s$ is a string containing only the character $\texttt{a}$.
2. Replace each $\texttt{a}$ in $s$ with $\texttt{b}$ and each $\texttt{b}$ with $\texttt{a}$ to get a string $t$, then append $t$ to $s$.
3. Repeat step 2 indefinitely to get the final $s$.

It can be observed that $s = \texttt{abbabaabbaababba}\cdots$, so the first level is a normal level, the second is a bonus level, the third is a bonus level, the fourth is a normal level, and so on.

Clearing the $i$-th level earns $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$.

N cleared all the bonus levels and ignored all the normal levels in a fit of anger, then uninstalled the game. Now, she wants to know her total score before uninstalling the game, modulo $10^9 + 7$.

Input Format

The first line contains a positive integer $n$, representing the number of levels in the game, given in binary.

The second line contains a positive integer $k$, representing the degree of the polynomial plus one.

The third line contains $k$ non-negative integers, $a_0, a_1, a_2, \cdots, a_{k-1}$, representing the coefficients of the polynomial.

Output Format

A single non-negative integer, representing N's total score before uninstalling the game, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

1000
3
3 2 1

Sample Output #1

110

Sample Input #2

11111100101
4
2 0 2 1

Sample Output #2

143901603

Sample Input #3

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

Sample Output #3

184740992

Notes/Hints

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

Thanks to s_r_f for providing the data.

见题面 Input 部分

见题面 Output 部分