Problem B
A happy new year?

For the past few years, Yichen has been carefully keeping track of his happiness every day, and noticed a strange pattern which lets him calculate exactly how happy he will be in a given day. It works as follows.

First, he has identified $n$ different things that happen very often, and their importance for his happiness can be ordered from least to most important. To find out how happy he will be on day $i$, he finds the most important thing which has happened in the last $k$ days (i.e in days $i-k+1, i-k+2, ..., i$), and if this was thing number $t$ on his list, his happiness on day $i$ will be exactly $w_ t$, which is a non-negative integer that he knows.

For example, the second thing on his list (i.e. the second least important thing which could happen) is if someone says hi on the bus when he’s on his way to lectures, and this would give him happiness $w_2$. If this is the most important thing that has happened in the past $k$ days, his happiness today will be $w_2$.

Recently he found a way to combine the happiness of many days into an overall happiness. In particular, the happiness of $d$ consecutive days is the geometric mean of the happiness of each of the days. Now he wants to know how happy the coming year will be.

Unfortunately, he doesn’t know what is going to happen, but he works under the assumption that the most important thing which happens on a day $i$ is some uniformly random thing from his list (his friends have complained that this is very unreasonable, but Yichen decided to ignore this). Furthermore, Yichen thinks that roots are very annoying (the most important thing on his list is tripping on a root, which will cause him to be very unhappy for a very long time), so he only wants to know the expected product of his happiness in all days in the coming year.

He has asked for your help to calculate this. In particular, you will be given an integer $n$, which is both the number of days of the year and the number of things on the list. You will also be given the values of $w_ i$. You should then calculate the expected value of Yichens happiness in the coming year, ignoring the first $k-1$ days. That is, if a sequence of $n$ integers are chosen independently and uniformly at random from the interval $[1,n]$, the maximum value $t$ in each subinterval of length $k$ calculated giving the value $w_ t$, and all of these $n-k+1$ values multiplied, what is the expected value $E$ of their product?

You should output $E \cdot n^ n$, which guarantees it’s an integer. Since the answer may be very large, output it modulo $998244353$.

Input

In the first there is an integer $1 \leq n \leq 400$ and an integer $1 \leq k \leq n$.

In the next line there are $n$ integers, the $i^{th}$ of which is the value of $0 \leq w_ i \leq 10^9$.

Output

Output a single line containing an integer, the expected happiness times $n^ n$ modulo $998244353$. It is guaranteed that the expected happiness times $n^ n$ is an integer.

2 2
1 2

7

5 3
2 4 1 3 5

190493

20 5
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

682753141