mahjong
暂无测试数据。
ame 是一个可爱的女孩子，她喜欢打麻将。
ame 找来了一副特殊的麻将，为了防止你不知道麻将的相关规则，在此给出一些定义：
- 这副麻将共含有 $m$ 种花色，有 $n$ 种不同的数字，大小分别为 $1$ 到 $n$。
- 一共有 $n\times m$ 种牌，每种牌为一个两两不同的二元组 $(x,y)$，表示这种牌数字为 $x$，花色为 $y$，每种牌都有 $4$ 张。其中 $1\leq x\leq n,1\leq y\leq m$。
- 一组面子可以为一组刻子或一组顺子。
- 定义一组顺子是三张花色相同、数字连续的牌。
- 定义一组刻子是三张花色和数字组合完全相同的牌。
- 定义一组对子是两张花色和数字组合完全相同的牌。
定义一个麻将牌可重集合 $S$ 是胡的当且仅当：
- 大小为 $3k+2$，其中 $k$ 为给定的数值。
- 能够被划分为 $k$ 组面子和一组对子。
游戏开始时，ame 从所有牌当中取出了一个大小为 $3k+2$ 的麻将牌集合 $S$，她想知道对于所有不同的 $S$，其中能胡的有多少个。
定义两个麻将牌集合 $S$ 和 $T$ 不同当且仅当存在一种牌，在 $S$ 中的出现次数和在 $T$ 中的出现次数不同。
对于所有数据，$4\leq n \leq 10^9$，$1\leq m\leq 10^9$，$1\leq k\leq 100$。
输入格式
输入共 $1$ 行 $3$ 个正整数 $n,m,k$。
输出格式
输出共 $1$ 行 $1$ 个整数，表示对 $998244353$ 取模之后的答案。
数据范围
对于所有数据，$4\leq n \leq 10^9$，$1\leq m\leq 10^9$，$1\leq k\leq 100$。
| 数据编号 | $n \leq$ | $m$ | $k\leq$ | 时间限制 |
|---|---|---|---|---|
| 1 | $9$ | $= 1$ | $4$ | 4s |
| 2,3,4,5,6 | $100$ | $\leq 10^9$ | $100$ | 4s |
| 7,8,9,10,11 | $10^9$ | $=n$ | $100$ | 4s |
| 12 | $10^9$ | $\leq 10^9$ | $1$ | 4s |
| 13 | $10^9$ | $\leq 10^9$ | $2$ | 4s |
| 14 | $10^9$ | $\leq 10^9$ | $3$ | 4s |
| 15 | $10^9$ | $\leq 10^9$ | $4$ | 4s |
| 16,17,18,19,20 | $10^9$ | $\leq 10^9$ | $30$ | 4s |
| 21,22,23,24,25 | $10^9$ | $\leq 10^9$ | $100$ | 4s |
2 1 1
2
3 1 1
9
100 100 30
960348259