[NOI Online 2021 提高组] 愤怒的小 N

极度愤怒的小 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$ 取模后的结果。

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

对于所有测试点：$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。$ | 测试点编号 | $\log_2n\le$ | $k\le$ | |:-:|:-:|:-:| | $1\sim2$ | $10$ |$500$ | | $3\sim4$ | $20$ | $500$ | | $5\sim8$ | $100$ | $500$ | | $9\sim10$ | $500$ | $500$ | | $11\sim12$ | $5\times 10^5$ | $1$ | | $13\sim16$ | $5\times 10^5$ | $100$ | | $17\sim20$ | $5\times 10^5$ | $500$ | 感谢 [s_r_f](https://www.luogu.com.cn/user/52518) 提供数据。