Scoring the Bonus Levels

Extreme‐angry Little N has just finished a game to vent his anger. The game consists of n levels numbered from 0 to n-1. Each level is either a normal level or a bonus level. The type of a level is determined by an infinite string s which is constructed as follows:

1. Initially, s is the string "a" (which represents a normal level).
2. Then, create a string t by replacing each character in s: replace every a with b and every b with a; and append t to the end of s.
3. Repeat step 2 indefinitely so that the resulting string is s.

Thus, the prefix of s of length n determines the level types. In this string, character a represents a normal level and b represents a bonus level. For example, the string begins as:

$$s = a\,b\,b\,a\,b\,a\,a\,b\,\cdots$$

One can prove that for each index i the character s[i] is given by:

$$ s[i]=\begin{cases}\texttt{a} &\text{if } \mathrm{popcount}(i)\text{ is even},\\ \texttt{b} &\text{if } \mathrm{popcount}(i)\text{ is odd},\end{cases} $$

where \(\mathrm{popcount}(i)\) denotes the number of 1's in the binary representation of \(i\). Through level i, one gains a score of \(f(i)\) points, where \(f(x)\) is a fixed polynomial of degree \(k-1\):

$$f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}.$$

Little N was so angry that he only cleared the bonus levels (i.e. those levels \(i\) for which \(\mathrm{popcount}(i)\) is odd) and ignored the normal levels before uninstalling the game. Now he wonders what his total score is modulo \(10^9+7\).

Your task is to compute the total score obtained from all bonus levels among the first n levels, modulo \(10^9+7\).

inputFormat

The first line contains two integers n and k (1 \leq n \leq 10^5, 1 \leq k \leq 10), where n is the total number of levels and k is the number of coefficients of the polynomial.

The second line contains k integers: a0, a1, ..., ak-1 (each coefficient's absolute value is at most 10⁹), which define the polynomial \(f(x)\).

outputFormat

Output a single integer: the total score obtained from all bonus levels (i.e. levels where the binary representation of the level number has an odd number of 1's), taken modulo \(10^9+7\).

sample

5 2
1 1

10

</p>