나머지 합

Snuke는 난수 생성기를 하나 발견했다. 이 생성기는 $1$ 이상 $N$ 이하의 정수를 하나 생성한다. 정수열 $A_1, A_2, \cdots, A_N$은 각 정수가 생성될 확률을 나타낸다. 정수 $i$ ($1 \leq i \leq N$)는 확률 $A_i / S$로 생성되며, 여기서 $S = \sum_{i=1}^{N} A_i$이다. 생성기를 실행할 때마다 정수를 생성하는 과정은 서로 독립적으로 이루어진다.

Snuke에게는 현재 값이 $0$인 정수 $X$가 있다. Snuke는 다음 연산을 원하는 만큼 몇 번이든 수행할 수 있다.

• 생성기로 정수 $v$를 생성하고, $X$를 $X + v \mod M$으로 바꾼다.

$X$가 $K$가 될 때까지 필요한 연산 횟수의 기댓값을 구하라. 이 기댓값을 기약분수 $P/Q$로 나타내면, $R \times Q \equiv P \mod 998244353$이고 $0 \leq R < 998244353$을 만족하는 정수 $R$이 하나만 존재한다. 이 $R$을 출력하라.

기댓값이 유한한 유리수임은 증명했다. 그러나 그 값을 $998244353$으로 나눈 나머지인 정수 표현이 정의될 수 있는지는 증명하지 못했다. 죄송하다. 다만 $0$으로 나누는 경우는 신경 쓰지 않아도 된다. 이 문제는 흡수 마르코프 연쇄로 모델링할 수 있으며, 모든 테스트에서 대응하는 기본 행렬이 $998244353$을 법으로 정의됨을 보장한다.

입력은 표준 입력으로 다음 형식으로 주어진다.

$N$ $M$ $K$

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

$X$가 $K$가 될 때까지 필요한 연산 횟수의 기댓값을 $998244353$으로 나눈 나머지를 출력한다.

• $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$
• 입력 값은 모두 정수이다.