down

题目描述

很多年前小 D 和小 T 在打 $n$ 个不同的游戏，初始两个人在所有游戏的等级都是 $0$。接下来的 $m$ 天，每天两个人都会分别选择一个游戏，并将自己在对应游戏的等级提高 $1$。即如果令 $d_i,t_i$ 分别表示小 D 和小 T 在第 $i$ 个游戏的等级，每一天会选择 $(i,j)$ 并将 $d_i,t_j$ 分别 $+1$。

如果某一天两个人选择了同一个游戏，他们会在聊天室看到对方并记录这个事件。现在很多年过去了，他们早已忘记了游戏账号，唯一记得的是 $n,m$ 的值，以及两人在这个过程中进行了 $x$ 次聊天。即在 $m$ 次选择的 $(i,j)$ 中，有恰好 $x$ 次满足 $i=j$。

他们想要知道，最终两人的游戏等级有多少种不同的可能。两种游戏等级 $(d,t)$ 和 $(d',t')$ 不同，当且仅当存在 $i$，使得 $d_i\ne d'_i$ 或 $t_i\ne t'_i$。答案对 $998244353$ 取模。注意如果两种不同的操作得到了一样的游戏等级，也只计算一次。

输入格式

一行三个整数 $n,m,x$，含义与题目描述中相同。

输出格式

一行一个整数，表示答案。

样例

样例 1 输入

3 1 1

样例 1 输出

3

样例 2 输入

3 1 0

样例 2 输出

6

样例 3 输入

314 1592 653

样例 3 输出

755768689

附加样例

见下发文件，第 $i$ 组下发样例符合第 $i$ 个子任务的限制。

数据范围与约定

对于全部数据，$2\le n\le 3000,0\le x\le m\le 3000$。