题目背景

第一分钟,$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$的值.

2
6
1 2 3 4 5 6

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);
}