某不科学的多重前缀求和¶

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

小A在做学园都市第零次高中模拟考试试卷时，发现了一道有意思的数学题，于是他决定结合算法知识进行数据范围加强。

给定正整数 \(n,m\) 、非负整数 \(k\) 以及系数 \(a_0,\ldots,a_k\) .定义

\[ F_0(x)=\sum_{i=0}^{k}a_ix^i \]

对正整数 \(t,x\) ，递归定义

\[ F_t(x)=\sum_{y=1}^{x}F_{t-1}(y) \]

求 \(F_m(n)\bmod2147483647\) 的非负最小剩余。每一层求和都包含端点一和 \(x\) .\(k=0\) 时初始函数是常数 \(a_0\) .

第一行三个整数 \(n,m,k\) .第二行 \(k+1\) 个整数，依次为 \(a_0,a_1,\ldots,a_k\) .

输出一行一个整数，表示答案，范围为 \([0,2147483646]\) .

3 2 2
1 2 1

5 3 0
7

1 7 3
1 2 3 4

第一组中，初始前三项为 \(4,9,16\) .一轮汇总得到 \(4,13,29\) ，第二轮在第三个位置的值为 \(4+13+29=46\) .

第二组的初始值恒为七，第二轮前五项为 \(7,21,42,70,105\) ，再求和得到 \(245\) .第三组只关心第一个位置，任意轮汇总后都保持 \(1+2+3+4=10\) .

对所有数据，\(1\le n\le2\times10^9\) ，\(1\le m\le10^7\) ，\(0\le k\le300\) ，\(1\le a_i\le2\times10^9\) .

分值比例	额外条件
100%	无额外条件