← 返回题目列表

AtCoder · abc297_f

I. 最小边界框 2

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

分数: 500 点

问题陈述

我们有一个网格 H 行和 W 列。

我们选择 K 该网格中的单元格均匀随机。 分数是包含所有选定单元格的最小矩形(其边缘平行于网格的轴)中的单元格数量。

求期望分数模数 998244353.

什么是有理数模 998244353? 我们可以证明所求的期望值始终是有理数。 而且,在这个问题的约束下,当值表示为 \frac{P}{Q} 由两个互质整数 P 和 Q,我们可以证明有一个唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。 找到这样的 R.

约束

  • 1\leq H,W \leq 1000
  • 1\leq K \leq HW
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W K

输出

打印答案。


示例输入 1

2 2 2

示例输出 1

665496238

分数等于 4 在以下两种情况下:如果单元格 选择 (1,1) 和 (2,2) ,或单元格 选择 (1,2) 和 (2,1) 。 其他四种情况得分为 2.

因此,预期分数等于 \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}。 自从 665496238 \times 3 \equiv 8\pmod{998244353},你应该打印 665496238.


示例输入 2

10 10 1

示例输出 2

1

示例输入 3

314 159 2653

示例输出 3

639716353