#P17497. [ICPC 2026 Wuhan I] Rook
[ICPC 2026 Wuhan I] Rook
Problem Description
There is an chessboard.
You need to place distinct rooks on this chessboard. The placement must satisfy all of the following conditions:
- Each cell contains at most one rook.
- Every row of the chessboard contains at least one rook.
- 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 .
Input Format
The input contains only one line.
This line contains three integers in order (), 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 .
2 2 3
24
5 3 4
0
353 442 899
623104742