Migrated from Lutece 3200 卡牌收集

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小u同学是个收集爱好者，在前面公园散完步之后，他来到了一家小卖部

这家小卖部有卡牌抽奖活动，规则如下:

一共$n$种卡牌，每种卡牌有无数张，第$i$种卡牌的权重是$w_i$，每次抽奖之间是相互独立的

每次抽奖抽到第$i$种卡牌的概率是$\frac{w_i}{\sum_{j=1}^nw_j}$

小u同学想要得到$m$种卡牌，他一共有抽$k$次的机会

为了权衡利弊，他想知道这种情况的概率是多少，由于小u呆头呆脑的，这个问题又交给了万能的你.

最后请输出得到这种情况的概率对998244353取模的结果

Input

第一行输入三个数$n$,$m$,$k$ 接下来输入$n$行，每行一个数，第$i$行表示$w_i$

Output

输出一个数，即小u抽奖$k$次最后得到$m$种卡牌的概率(对998244353取模)

Samples

2 1 2
2
1

221832079

Constraints

$1\leq m \leq n \leq 50$ $1\leq k \leq 50$ $0\lt w_{i}$ $\sum w_i \lt 998244353$

Note

样例的概率为$\frac{5}{9}$ 本题最终的结果需要进行取模，涉及到乘法逆元的知识点，同学们可以提前进行学习 乘法逆元的求解

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming