3555. [NOI Online 2021 1st] 愤怒的小N

(测试数据不够，请移步洛谷本题)

【题目描述】

极度愤怒的小 $N$ 通关了一款游戏来泄愤。 这款游戏共有 $n$ 关，分别为第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关。这些关卡中有一些是普通关卡，另一些则是奖励关卡。 这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 $a$ 表示普通关卡，用字符 $b$ 表示奖励关卡，那么第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关依次排列形成的字符串是一个无穷字符串 $s$ 的前缀，且 $s$ 可以按照如下方式构造：

$1$. 初始时 $s$ 为包含单个字符 $a$ 的字符串。

$2$. 将 $s$ 的每个字符 $a$ 替换成字符 $b$，每个字符 $b$ 替换成字符 $a$ 得到字符串 $t$，然后将 $t$ 拼接到 $s$ 后。

$3$. 不断执行 $2$. 得到的字符串就是最终的 $s$。

可以发现 $s=abbabaabbaababba$，所以这款游戏的第 $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

【样例1解释】

这款游戏共有 $8$ 关，通关第 $i$ 关可以得到 $3+2*i+i^2$ 分。第 $1,2,4,7$ 关为奖励关，小 $N$ 通过这几关分别得到了 $6,11,27,66$ 分，共 $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

【数据规模与约定】

测试点 $1 \sim 2$：$\log_2n < 10，k \le 500$；

测试点 $3 \sim 4$：$\log_2n < 20，k \le 500$；

测试点 $5 \sim 8$：$\log_2n < 100，k \le 500$；

测试点 $9 \sim 10$：$\log_2n < 500，k \le 500$；

测试点 $11 \sim 12$：$\log_2n < 5 \times 10^5，k \le 1$；

测试点 $13 \sim 16$：$\log_2n < 5 \times 10^5，k \le 100$；

测试点 $17 \sim 20$：$\log_2n < 5 \times 10^5，k \le 500$；

对于所有测试点：

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

【来源】

NOI Online 2021 1st