You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

现有 $n$ 个互不相同的数据元素，需要将它们放入一个大小为 $m$ 的哈希表中（哈希表的索引编号为 $0$ 到 $m-1$）。假设每个数据都可以被映射到 $m$ 个槽位中的任意一个，且映射到每个槽位的概率是均等的。这意味着总共有 $m^n$ 种不同的映射方案。请你计算：在所有可能的映射方案中，有多少种方案满足“恰好有 $t$ 个槽位是没有出现哈希冲突的”？由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

当两个或更多的数据被映射到同一个槽位时，就会发生“哈希冲突”。

Input Format

第一行输入三个整数 $n，m，t$ 表示数据的个数，哈希表的大小，没有出现冲突的索引个数。

Output Format

输出一个整数表示方案数

Sample

Input1：

4 2 0

Output1：

6

Input2:

3 2 1

Output2:

8

Hint

$1 \le n, m \le 5000,1 \le t \le n$。