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

    ID: 5309 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-奇偶性分析数位 DP指数生成函数截断幂级数二项式定理连续点值插值阶乘逆元预处理秦九韶算法

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

题目描述

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

这款游戏共有 nn 关,分别为第 00 关、第 11 关、第 22 关、⋯\cdots、第 n−1n-1 关。这些关卡中有一些是普通关卡,另一些则是奖励关卡。

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

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

可以发现 s=abbabaabbaababba⋯s=\texttt{abbabaabbaababba}\cdots,所以这款游戏的第 00 关是普通关卡,第 11 关 是奖励关卡,第 22 关是奖励关卡,第 33 关是普通关卡,以此类推。

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

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

输入格式

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

第二行一个正整数 kk,表示多项式的次数加一。

第三行 kk 个非负整数,分别为 a0,a1,a2,⋯ ,ak−1a_0,a_1,a_2,\cdots,a_{k-1},表示多项式的各项系数。

输出格式

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

样例 #1

样例输入 #1

1000
3
3 2 1

样例输出 #1

110

样例 #2

样例输入 #2

11111100101
4
2 0 2 1

样例输出 #2

143901603

样例 #3

样例输入 #3

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

样例输出 #3

184740992

提示

对于所有测试点:0≤log⁡2n<5×1050\le \log_2n<5\times 10^5,1≤k≤5001\le k\le 500,0≤ai<109+70\le a_i < 10^9 + 7,ak−1≠0。a_{k-1}\ne 0。

测试点编号 log⁡2n≤\log_2n\le k≤k\le
1∼21\sim2 1010 500500
3∼43\sim4 2020
5∼85\sim8 100100
9∼109\sim10 500500
11∼1211\sim12 5×1055\times 10^5 11
13∼1613\sim16 100100
17∼2017\sim20 500500