시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB0000.000%

문제

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, and we guarantee that in all tests, the corresponding fundamental matrices can be defined modulo $998\,244\,353$.

입력

Input is given from Standard Input in the following format:

$N$ $M$ $K$

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

출력

Output the expected number of operations until $X$ becomes $K$, modulo $998\,244\,353$.

제한

  • $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.

예제 입력 1

2 3 1
1 1

예제 출력 1

2

예제 입력 2

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

예제 출력 2

439915532