小 $\omega$ 的牌（$\texttt{c}$）

题目描述

小 $\omega$ 有写有 $1\sim n$ 的卡牌各 $m$ 张。初始他每张卡牌手中各有 $a_i$ 张，剩余的均在牌山中。保证 $\sum_{i=1}^na_i=m$。

小 $\omega$ 希望他所有的卡牌写有同样的数字，然而他不会概率论，所以只会随机挑选一张打出去。

与此同时，牌山也会随机选择一张牌山中的卡牌发给他。

注意，这两件事同时发生。换句话说，你可以理解成小 $\omega$ 从 $m$ 张牌中随机选择一张，而牌山从 $(n-1)m$ 张牌中随机选择一张后小 $\omega$ 将选择的这张牌与牌山交换。

小 $\omega$ 不想等太长时间，于是他想至少期望他打出去多少张牌后他手中的所有牌写有同样的数字，对 $998244353$ 取模。

另外，小 $\omega$ 希望多玩几局卡牌游戏，但是都使用同一副牌。也就是说，本题有 $t$ 组测试数据，$t$ 组测试数据唯一不同的是初始手中卡牌数量，也就是 $\{a\}$。

输入格式

第一行三个正整数 $n,m,t$，表示卡牌种类数，卡牌数量和测试数据组数。

接下来 $t$ 行，每行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。保证 $\sum_{i=1}^na_i=m$。

输出格式

$t$ 行，每行一个整数，表示期望打出的牌数，对 $998244353$ 取模。

样例一

input

2 3 2
0 3
1 2

output

0
9

explanation

$a_1=0,a_2=3$ 时，初始状态就写有同样数字，故答案为 $0$。

$a_1=1,a_2=2$ 时，当且仅当打出 $1$，摸进 $2$ 时才会使得所有牌写有同样数字，否则将变为等价状态。其发生概率为 $\frac{1}{9}$，故答案为 $9$。

样例二

input

6 7 2
1 2 0 3 0 1
1 1 1 2 2 0

output

825297686
559099197

限制与约定

本题采用捆绑测试。不开启依赖。

对于 $100\%$ 的数据：$1\leq m\leq10^5$，$1\leq n\leq 5\times 10^3$，$t\leq200$，$0\leq a_i\leq m$，$\sum_{i=1}^na_i=m$。