背景

第一分钟，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$ 的值。

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