Description

Now there is a combat-aerobics routine consisting of $k$ kinds of moves, with a total of $N$ moves.

It is known that the power of moves $1, 2, \cdots, k$ is $a[1\cdots k]$.

Also, if the first move is immediately followed by the second move, then the power will additionally increase by $a[1]+a[2]$.

If the second move is immediately followed by the third move, then the power will additionally increase by $a[2]+a[3]$.

……

If the $k$-th move is immediately followed by the first move, then the power will additionally increase by $a[k]+a[1]$.

Please find the expected power of the final routine.

Of course, you still need to take it modulo the great modulus $19491001$.

Input Format

The first line contains a positive integer $N$.

The second line contains a positive integer $k$.

The third line contains $k$ positive integers $a[1\cdots k]$.

Output Format

One line, a positive integer representing the expected power modulo $19491001$.

2
6
1 2 3 4 5 6

16242509

Hint

Sample Explanation

$x-y$ means the first move is $x$ and the second move is $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$.

It is guaranteed for all testdata that $1 \leq a[i] \leq 10^7$.

Note: This problem uses bundled tests.

A small hint:

You can use the following $\texttt{inv(}x\texttt{)}$ to compute the modular inverse of $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);
}

Translated by ChatGPT 5