33OJ
登录 注册

#P17497. [ICPC 2026 Wuhan I] Rook

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

[ICPC 2026 Wuhan I] Rook

Problem Description

There is an N×MN\times M chessboard.

You need to place KK distinct rooks on this chessboard. The placement must satisfy all of the following conditions:

  1. Each cell contains at most one rook.
  2. Every row of the chessboard contains at least one rook.
  3. Every column of the chessboard contains at least one rook.

Please find the total number of valid placements. Since the answer may be very large, you only need to output the result modulo 998244353998244353.

Input Format

The input contains only one line.

This line contains three integers N,M,KN,M,K in order (1≤N,M,K≤1051 \le N,M,K \le 10^5), representing the number of rows and columns of the chessboard, and the number of rooks to place, respectively.

Output Format

Output one line containing an integer, the number of valid placements modulo 998244353998244353.

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