There are $n$ balls arranged in a row, numbered $0$ to $n-1$, all initially white. Little H repeats the following operation twice: randomly choose $m$ balls from the $n$ balls and paint them black (a ball can be painted black multiple times). Little H has a special preference for the black ball with the smallest index. She wants to know the expected value of $F(A)$, where $A$ is the index of the smallest black ball, and $F(x)$ is a polynomial of degree at most $m$. $F(A)$ denotes the value of the polynomial at $x=A$.
Input
The first line contains two integers $n$ and $m$.
The second line contains $m+1$ integers, where the $i$-th integer is $F(i-1)$.
Output
Output a single integer representing the value of $E \times {\binom{n}{m}}^2 \pmod{998244353}$, where $E$ is the expected value of $F(A)$.
Examples
Input 1
8 5 45856608 386378255 106492167 28766400 272276589 93721672
Output 1
321347828
Subtasks
- For $10\%$ of the data, $n \leq 10$, $m \leq 5$.
- For $20\%$ of the data, $n \leq 100$, $m \leq 100$.
- For $30\%$ of the data, $n \leq 1000$, $m \leq 1000$.
- For another $5\%$ of the data, $m \leq 1000000$, and it is guaranteed that $F(x)=1$.
- For another $5\%$ of the data, $m \leq 5000$, and it is guaranteed that $F(x)=x$.
- For another $10\%$ of the data, $m \leq 5000$, and it is guaranteed that $F(x)=x^m$.
- For $70\%$ of the data, $m \leq 5000$.
- For $80\%$ of the data, $m \leq 20000$.
- For $100\%$ of the data, $n \leq 998244353$, $m \leq 1000000$.