33OJ
登录 注册

#P17497. [ICPC 2026 Wuhan I] Rook

    ID: 20225 远端评测题 6000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>多项式Stirling 数快速数论变换 NTTICPC2026省赛/邀请赛湖北

[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 取模后的结果。

2 2 3
24
5 3 4
0
353 442 899
623104742