#P17778. [ICPC 2026 Wuhan I] Rook

[ICPC 2026 Wuhan I] Rook

题目描述

有一个 N×MN\times M 的棋盘。

你需要在这个棋盘上放置 KK 个互不相同的 “车”(即不同的棋子)。放置方案必须满足以下所有条件:

  1. 每个格子至多放置一个 “车”。
  2. 棋盘的每一行都至少有一个 “车”。
  3. 棋盘的每一列都至少有一个 “车”。

请你求出满足条件的放置方案总数。由于答案可能很大,你只需要输出方案数对 998244353998244353 取模后的结果。

输入格式

输入仅包含一行。

这一行依次包含三个整数 N,M,KN,M,K(1≤N,M,K≤1051 \le N,M,K \le 10^5),分别表示棋盘的行数、列数以及需要放置的 “车” 的数量。

输出格式

输出一行包含一个整数,表示合法的放置方案总数对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

2 2 3

输出 #1

24

输入输出样例 #2

输入 #2

5 3 4

输出 #2

0

输入输出样例 #3

输入 #3

353 442 899

输出 #3

623104742