Snuke 发现了一个随机数生成器。它会生成一个 $1$ 到 $N$（包含 $1$ 和 $N$）之间的整数。整数序列 $A_1, A_2, \dots, A_N$ 代表了每个整数被生成的概率。整数 $i$ ($1 \le i \le N$) 被生成的概率为 $A_i/S$，其中 $S = \sum_{i=1}^N A_i$。每次执行生成器时，生成整数的过程都是相互独立的。

Snuke 有一个整数 $X$，初始值为 $0$。他可以执行任意次数以下操作：

• 使用生成器生成一个整数 $v$，并将 $X$ 更新为 $(X + v) \pmod M$。

求 $X$ 变为 $K$ 所需的操作次数的期望值，并将其对 $998244353$ 取模。更正式地说，将期望操作次数表示为不可约分数 $P/Q$。那么，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R < 998244353$，请输出这个 $R$。

我们可以证明，$X$ 变为 $K$ 所需的操作次数的期望值是一个有限的有理数。虽然我们没有证明其模 $998244353$ 的整数表示一定存在，但请不必担心除以 $0$ 的情况。更准确地说，我们可以将此问题建模为吸收马尔可夫链（https://en.wikipedia.org/wiki/Absorbing_Markov_chain），并且我们保证在所有测试用例中，相应的基本矩阵在模 $998244353$ 下都是可定义的。

输入格式

输入通过标准输入按以下格式给出：

$N \ M \ K$ $A_1 \ A_2 \ \dots \ A_N$

数据范围

• $1 \le N \le \min(500, M - 1)$
• $2 \le M \le 10^{18}$
• $1 \le K \le M - 1$
• $1 \le A_i \le 100$
• 输入中的所有值均为整数。

输出格式

输出 $X$ 变为 $K$ 所需的操作次数的期望值，对 $998244353$ 取模。

样例

样例输入 1

2 3 1
1 1

样例输出 1

2

样例输入 2

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

样例输出 2

439915532