← 返回题目列表

AtCoder · arc113_d

D. 天空反射器

中文机器翻译题面 查看原题

分数: 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