Background

In the first minute, CYJian said, “There should be some form.” So there were $k$ kinds of moves.

In the second minute, CYJian said, “There should be energy.” So there was a combat-aerobics routine with a total of $N$ moves composed of the $k$ kinds of moves.

In the third minute, CYJian said, “There should be math.” So there was a definition of the power of a routine.

In the fourth minute, CYJian said, “Numbers should be small.” So there was a great modulus $19491001$.

In the fifth minute, CYJian said, “There should be a pattern.” So there was a way to compute the power of a routine.

In the sixth minute, CYJian said, “There should be limits.” So there were time and memory limits and Constraints.

In the seventh minute, CYJian said, “There should be an answer.” So there was this problem for you to solve.

……

In the $*$-th minute, the expert Imagine said, “The testdata is too easy.” So the newbie problem setter went crazy. (See Constraints for details.)

Problem 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