P7342 "MdOI R4" Destiny

The first sentence of T5 is false.

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}$.

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 one integer per line, representing the weight of sequence $a$ modulo $998244353$.

[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. |Test Point ID|$n\le$|$k$| |:-|:-|:-| |$1\sim 3$|$5000$|No special restrictions| |$4\sim 10$|$10^5$|No special restrictions| |$11\sim 15$|No special restrictions|$=60928$| |$16\sim 25$|No special restrictions|No special restrictions| 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