Sequence Weight Sum

We are given a sequence \(a_0,a_1,\ldots,a_{n-1}\) whose weight \(v(a)\) is defined recursively as follows (note that indices start at 0):

• If \(n=1\) then \(v(a)=a_0\).
• If \(n>1\) then
  \[ v(a_0,a_1,\ldots,a_{n-1})=\sum_{i=0}^{n-2}\;\sum_{j=0}^{n-i-1} v(a_j,a_{j+1},\ldots,a_{j+i}). \] (In other words, the weight is the sum of the weights of all proper contiguous subarrays.)

The sequence \(a\) is generated by taking an input sequence \(b_0,b_1,\ldots,b_{k-1}\) and repeating it: for each \(i\), \(a_i=b_{i\;\bmod\;k}\). Given \(n,k\) and the \(b\) sequence, compute \(v(a)\) modulo \(998244353\).

Note: In the definition the whole sequence is not considered as a proper subarray of itself, which makes the recursion well–founded.

inputFormat

The first line contains two integers \(n\) and \(k\) (the length of the sequence \(a\) and the length of the repeating block).
The second line contains \(k\) integers: \(b_0, b_1, \ldots, b_{k-1}\).
The full sequence \(a\) is generated as \(a_i = b_{i\;\bmod\;k}\) for \(0 \le i < n\).

outputFormat

Output a single integer: the weight \(v(a)\) modulo \(998244353\).

sample

3 2
1 2

8