Expected Product of Sequence After Random Increments

Consider a sequence (a_1, a_2,\dots,a_n) of length (n) initialized with zeros. You are given positive integers (m) and (c) and (n-m+1) positive integers (b_1,b_2,\dots,b_{n-m+1}). Then, you perform (c) independent operations on the sequence. In each operation, an integer (x) is chosen from (1) to (n-m+1) with probability [ p_x = \frac{b_x}{B}, \quad \text{where } B = \sum_{i=1}^{n-m+1} b_i, ] and the contiguous segment (a_x, a_{x+1}, \dots, a_{x+m-1}) is increased by (1) each.

After all operations, let the final sequence be (a_1, a_2, \dots, a_n) (note that (n = n-m+1 + m-1)). The task is to compute the expected value of the product of all elements, i.e., [ E\Bigl[\prod_{i=1}^{n}a_i\Bigr]. ] Since the answer may not be an integer, output the result modulo (998244353).

Mathematically, using the multinomial expansion one may show that [ E\Bigl[\prod_{i=1}^{n}a_i\Bigr] = \frac{1}{B^c} \sum_{k_1+\cdots+k_{n-m+1}=c} \binom{c}{k_1,k_2,\dots,k_{n-m+1}} \Biggl( \prod_{i=1}^{n} \Bigl( \sum_{{x:, i\in [x,x+m-1]}} k_x \Bigr)\Biggr) \prod_{x=1}^{n-m+1}b_x^{k_x}, ] where the sum is taken over all nonnegative integers (k_1,k_2,\dots,k_{n-m+1}) summing to (c), and for each index (i) (with (1 \le i \le n) and (n=n-m+1+m-1)), the inner sum is over all indices (x) such that (a_i) is affected by the choice (x) (i.e. (i\in [x,x+m-1])).

You are guaranteed that (n) and (c) are such that a brute-force (complete search) solution over the multinomial distributions is feasible.

inputFormat

The input consists of two lines. The first line contains three integers (n), (m) and (c) (with (n \ge m)). The second line contains (n-m+1) positive integers: (b_1,b_2,\dots,b_{n-m+1}).

outputFormat

Output a single integer, the expected product (\prod_{i=1}^{n} a_i) modulo (998244353).

sample

3 2 2
1 1

1