Description

Note that in this problem, indices start from $0$.

For a sequence $\{a_i\}$ of length $n$, its weight $v(a)$ is defined as:

• When $n=1$, $v(a)=a_0$.
• When $n>1$, it is the sum of the weights of all its subsegments, that is, $v(a_0,a_1,\ldots,a_{n-1})=\sum\limits_{i=0}^{n-2}\sum\limits_{j=0}^{n-i-1}v(a_j,a_{j+1},\ldots,a_{j+i})$.

Given a sequence, compute its weight, and output the answer modulo $998244353$.

The sequence is generated as follows: input a sequence $b_0,b_1,\cdots,b_{k-1}$, then $a_i=b_{i\bmod k}$.

Input Format

The first line contains $n,k$, representing the length of sequence $a$ and the length of sequence $b$.

The second line contains $b_0,b_1,\cdots,b_{k-1}$, with the meaning described above.

Output Format

Output one integer per line, representing the weight of sequence $a$ modulo $998244353$.

4 3
3 4 6

104

10 10
2 5 3 8 4 5 2 19 3 6

219856

Hint

[Sample Explanation #1]

Generate the sequence $a=[3,4,6,3]$, then:

• $v(3,4)=v(3)+v(4)=7$
• $v(4,6)=v(4)+v(6)=10$
• $v(6,3)=v(6)+v(3)=9$
• $v(3,4,6)=v(3)+v(4)+v(6)+v(3,4)+v(4,6)=30$
• $v(4,6,3)=v(4)+v(6)+v(3)+v(4,6)+v(6,3)=32$
• $v(3,4,6,3)=v(3)+v(4)+v(6)+v(3)+v(3,4)+v(4,6)+v(6,3)+v(3,4,6)+v(4,6,3)=104$

[Constraints]

This problem does not use bundled tests.

There are $25$ test points in total, and each test point is worth $4$ points.

For $100\%$ of the testdata: $1\le n\le 10^9$，$1 \le k \le 10^5$，$0\le a_i\le 998244352$。

Thanks to $\rm\textcolor{black}{J}\textcolor{red}{ohnVictor}$ for contributing to this problem.

Translated by ChatGPT 5