There is a sequence $a_1, a_2, \dots, a_n$ of length $n$. Initially, all elements of the sequence are $0$. You are given positive integers $m$, $c$, and $(n - m + 1)$ positive integers $b_1, b_2, \dots, b_{n-m+1}$.
Perform $c$ operations on the sequence $a_1, a_2, \dots, a_n$. Each operation is as follows: * Randomly choose an integer $1 \le x \le n - m + 1$, where the probability of choosing $y$ ($1 \le y \le n - m + 1$) is $\frac{b_y}{\sum_{i=1}^{n-m+1} b_i}$. Increment $a_x, a_{x+1}, \dots, a_{x+m-1}$ by $1$.
The choices of $x$ in the $c$ operations are independent.
Calculate the expected value of the product of all elements in the sequence after the operations are completed. To avoid floating-point output, you need to output the answer modulo $998244353$.
Input
Read from standard input. The first line contains three integers $n, m, c$, representing the sequence length, the operation interval length, and the number of operations, respectively. The second line contains $n - m + 1$ integers $b_1, \dots, b_{n-m+1}$, describing the weights for the random choice.
Output
Output to standard output. Output a single integer representing the expected value of the product of all numbers in the sequence after $c$ operations, modulo $998244353$.
Examples
Input 1
3 2 2 1 1
Output 1
1
Note 1
When the $x$ chosen in the two operations are different, the final sequence is $1, 2, 1$, and the product of the elements is $2$. Otherwise, the sequence is $2, 2, 0$ or $0, 2, 2$, and the product of the elements is $0$ in both cases. The probability that the $x$ chosen in the two operations are different is $\frac{1}{2}$, so the output is $2 \times \frac{1}{2} = 1$.
Input 2
10 3 10 1 2 3 4 5 6 7 8
Output 2
721023399
Input 3
20 12 98765 9 8 7 6 5 4 3 2 1
Output 3
560770686
Subtasks
For all test data, $2 \le m \le n \le 50$, $1 \le c < 998244353$, and for $1 \le i \le n - m + 1$, $1 \le b_i \le 10^5$.
- Subtask 1 (10%): $m \le 8$.
- Subtask 2 (20%): $m \le 16$.
- Subtask 3 (15%): $n \le 20, c \le n$.
- Subtask 4 (15%): $n \le 30, c \le n$.
- Subtask 5 (15%): $n \le 40, c \le n$.
- Subtask 6 (15%): $c \le n$.
- Subtask 7 (10%): No special restrictions.