水の造题

题目背景

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

题目描述

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

输入输出格式

输入格式


第一行,一个正整数$N$ 第二行,一个正整数$k$ 第三行,$k$个正整数$a[1...k]$

输出格式


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

输入输出样例

输入样例 #1

2
6
1 2 3 4 5 6

输出样例 #1

16242509

说明

样例解释: ``` 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 = 16242501 (mod 19491001) ans = 49 * 16242501 mod 19491001 = 16242509 ``` $Subtask 1$($20 pts$):$1 \leq N \leq 10 \qquad 1 \leq k \leq 7$ $Subtask 2$($20 pts$):$1 \leq N \leq 10^6 \qquad 1 \leq k \leq 7$ $Subtask 3$($20 pts$):$1 \leq N \leq 10^{40000} \qquad 1 \leq k \leq 7$ $Subtask 4$($20 pts$):$1 \leq N \leq 10^{10^6} \qquad 1 \leq k \leq 7$ $Subtask 5$($20 pts$):$1 \leq N \leq 10^{10^6} \qquad 1 \leq k \leq 10^6$ 保证所有的数据: $1 \leq a[i] \leq 10^7$ ## 注意:本题捆绑测试 小提示: 可以用下面的inv(x)求出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); } ```