分数: 600 点
问题陈述
在网格中 N 水平行和 M 垂直的方格列,我们将在它们之间写一个整数 1 和 K (含)在每个方块上并定义序列 A, B 如下:
- 对于每个 i=1,\dots, N, A_i 是写在方框中的最小值 i第行;
- 对于每个 j=1,\dots, M, B_j 是写在方框中的最大值 j- 第列。
鉴于 N, M, K,找出可以的不同序列对的数量 (A, B),模数 998244353.
约束
- 1 \leq N,M,K \leq 2\times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K
输出
打印可以的不同序列对的数量 (A, B),模数 998244353.
示例输入 1
2 2 2
示例输出 1
7
(A_1,A_2,B_1,B_2) 可以 (1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2),或 (2,2,2,2) - 有七名候选人。
示例输入 2
1 1 100
示例输出 2
100
示例输入 3
31415 92653 58979
示例输出 3
469486242