406863: GYM102586 C Sum Modulo

Snuke found a random number generator. It generates an integer between $$$1$$$ and $$$N$$$ (inclusive). An integer sequence $$$A_1, A_2, \cdots, A_N$$$ represents the probability that each of these integers is generated. The integer $$$i$$$ ($$$1 \leq i \leq N$$$) is generated with probability $$$A_i / S$$$, where $$$S = \sum_{i=1}^{N} A_i$$$. The process of generating an integer is done independently each time the generator is executed.

Snuke has an integer $$$X$$$, which is now $$$0$$$. He can perform the following operation any number of times:

• Generate an integer $$$v$$$ with the generator and replace $$$X$$$ with $$$X + v \mod M$$$.

Find the expected number of operations until $$$X$$$ becomes $$$K$$$, and print it modulo $$$998244353$$$. More formally, represent the expected number of operations as an irreducible fraction $$$P/Q$$$. Then, there exists a unique integer $$$R$$$ such that $$$R \times Q \equiv P \mod 998244353,\ 0 \leq R < 998244353$$$, so print this $$$R$$$.

We can prove that the expected number of operations until $$$X$$$ becomes $$$K$$$ is a finite rational number. However, we did **not** prove its integer representation modulo $$$998244353$$$ can be defined. Our sincerest apologies. Nonetheless, you don't have to worry about division by $$$0$$$. More precisely, We can model this problem as an absorbing markov chain( https://en.wikipedia.org/wiki/Absorbing_Markov_chain), and we guarantee that in all tests, the corresponding fundamental matrices can be defined modulo $$$998244353$$$.

Input is given from Standard Input in the following format:

$$$N$$$ $$$M$$$ $$$K$$$

$$$A_1$$$ $$$A_2$$$ $$$\cdots$$$ $$$A_N$$$

Constraints:

• $$$1 \leq N \leq \min(500,M-1)$$$
• $$$2 \leq M \leq 10^{18}$$$
• $$$1 \leq K \leq M-1$$$
• $$$1 \leq A_i \leq 100$$$
• All values in input are integers.

Output the expected number of operations until $$$X$$$ becomes $$$K$$$, modulo $$$998244353$$$.

2 3 1
1 1

2

10 100 50
1 2 3 4 5 6 7 8 9 10

439915532