题目描述

极度愤怒的小 N 通关了一款游戏来泄愤。

这款游戏共有 $n$ 关，分别为第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关。这些关卡中有一些是普通关卡，另一些则是奖励关卡。

这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 $\texttt{a}$ 表示普通关卡，用字符 $\texttt{b}$ 表示奖励关卡，那么第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关依次排列形成的字符串是一个无穷字符串 $s$ 的前缀，且 $s$ 可以按照如下方式构造：

1. 初始时 $s$ 为包含单个字符 $\texttt{a}$ 的字符串。
2. 将 $s$ 的每个字符 $\texttt{a}$ 替换成字符 $\texttt{b}$，每个字符 $\texttt{b}$ 替换成字符 $\texttt{a}$ 得到字符串 $t$，然后将 $t$ 拼接到 $s$ 后。
3. 不断执行 2. 得到的字符串就是最终的 $s$。

可以发现 $s=\texttt{abbabaabbaababba}\cdots$，所以这款游戏的第 $0$ 关是普通关卡，第 $1$ 关 是奖励关卡，第 $2$ 关是奖励关卡，第 $3$ 关是普通关卡，以此类推。

通过游戏的第 $i$ 关可以得到 $f(i)$ 分，其中 $f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}$ 是一个固定的 $k-1$ 次多项式。

小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 $10^9+7$ 取模后的结果。

输入格式

第一行一个正整数 $n$，表示游戏的关卡数目。为方便，$n$ 以二进制表示给出。

第二行一个正整数 $k$，表示多项式的次数加一。

第三行 $k$ 个非负整数，分别为 $a_0,a_1,a_2,\cdots,a_{k-1}$，表示多项式的各项系数。

输出格式

一行一个非负整数，表示小 N 卸载游戏前的总得分对 $10^9 + 7$ 取模后的结果。

样例

样例输入 1

1000
3
3 2 1

样例输出 1

110

样例输入 2

11111100101
4
2 0 2 1

样例输出 2

143901603

样例输入 3

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

样例输出 3

184740992

数据范围与提示

对于所有测试点：$0\le \log_2n<5\times 10^5$，$1\le k\le 500$，$0\le a_i \le 10^9 + 6$，$a_{k-1}\ne 0$。