P5011 水の造题

第一分钟，CYJian 说：“要有样子。”于是便有了 $k$ 种动作。 第二分钟，CYJian 说：“要有活力。”于是便有了 $k$ 种动作组成的总动作数为 $N$ 的搏击操。 第三分钟，CYJian 说：“要有数学。”于是便有了一套搏击操的威力。 第四分钟，CYJian 说：“数字要小。”于是便有了一个伟大的模数 $19491001$。 第五分钟，CYJian 说：“要有规律。”于是便有了一套搏击操威力的计算方法。 第六分钟，CYJian 说：“要有限制。”于是便有了时空限制以及数据范围。 第七分钟，CYJian 说：“要有答案。”于是便有了这道题让你做掉。 …… 第 $*$ 分钟，巨佬 Imagine 说：“数据太水。”于是蒟蒻出题人疯了。（详见数据范围）

现在有一套由 $k$ 种动作组成的动作总数为 $N$ 的搏击操。 已知第 $1, 2, \cdots, k$ 个动作的威力为 $a[1\cdots k]$。 且如果第一个动作后紧接着第二个动作，则威力会额外加上 $a[1]+a[2]$。 如果第二个动作后紧接着第三个动作，则威力会额外加上 $a[2]+a[3]$。 …… 如果第 $k$ 个动作后紧接着第一个动作，则威力会额外加上 $a[k]+a[1]$。 请求出最后动作的期望威力。 当然，还是要用伟大的模数 $19491001$ 来膜一膜的。

第一行，一个正整数 $N$。 第二行，一个正整数 $k$。 第三行，$k$ 个正整数 $a[1\cdots k]$。

一行，一个正整数表示期望的威力模 $19491001$ 的值。

### 样例解释 $x-y$ 表示第一个动作为 $x$，第二个动作为 $y$。 - $1-1$：$1+1=2$； - $1-2$：$1+2+(1+2)=6$； - $1-3$：$1+3=4$； - $1-4$：$1+4=5$； - $1-5$：$1+5=6$； - $1-6$：$1+6=7$； - $2-1$：$2+1=3$； - $2-2$：$2+2=4$； - $2-3$：$2+3+(2+3)=10$； - $2-4$：$2+4=6$； - $2-5$：$2+5=7$； - $2-6$：$2+6=8$； - $3-1$：$3+1=4$； - $3-2$：$3+2=5$； - $3-3$：$3+3=6$； - $3-4$：$3+4+(3+4)=14$； - $3-5$：$3+5=8$； - $3-6$：$3+6=9$； - $4-1$：$4+1=5$； - $4-2$：$4+2=6$； - $4-3$：$4+3=7$； - $4-4$：$4+4=8$； - $4-5$：$4+5+(4+5)=18$； - $4-6$：$4+6=10$； - $5-1$：$5+1=6$； - $5-2$：$5+2=7$； - $5-3$：$5+3=8$； - $5-4$：$5+4=9$； - $5-5$：$5+5=10$； - $5-6$：$5+6+(5+6)=22$； - $6-1$：$6+1+(6+1)=14$； - $6-2$：$6+2=8$； - $6-3$：$6+3=9$； - $6-4$：$6+4=10$； - $6-5$：$6+5=11$； - $6-6$：$6+6=12$。 $2+6+4+5+6+7+3+4+10+6+7+8+4+5+6+14+8+9+5+6+7+8+18+10+6+7+8+9+10+22+14+8+9+10+11+12=294$。 $294/36=49/6$。 $1/6 \equiv 16242501 \pmod{19491001}$。 $ans = 49 \times 16242501 \bmod 19491001 = 16242509$。 Subtask 1（20 pts）：$1 \leq N \leq 10$，$1 \leq k \leq 7$； - Subtask 2（20 pts）：$1 \leq N \leq 10^6$，$1 \leq k \leq 7$； - Subtask 3（20 pts）：$1 \leq N \leq 10^{40000}$，$1 \leq k \leq 7$； - Subtask 4（20 pts）：$1 \leq N \leq 10^{10^6}$，$1 \leq k \leq 7$； - Subtask 5（20 pts）：$1 \leq N \leq 10^{10^6}$，$1 \leq k \leq 10^6$。 保证所有的数据：$1 \leq a[i] \leq 10^7$。 **注意：本题捆绑测试。** 小提示： 可以用下面的 $\texttt{inv(}x\texttt{)}$ 求出 $x$ 的逆元： ``` long long mod = 19491001; long long quick_pow(long long x, int k) { long long res = 1; while(k) { if(k & 1) res = res * x % mod; x = x * x % mod; k >>= 1; } return res; } long long inv(long long x) { return quick_pow(x, mod - 2); } ```