Score : $500$ points

问题陈述

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

在这个网格中，我们随机均匀选择 $K$ 个单元格。得分是包含所有选定单元格的最小矩形（其边与网格轴平行）中的单元格数量。

求得分的期望值模 $998244353$。

什么是模 $998244353$ 下的有理数？我们可以证明所求的期望值始终是一个有理数。此外，在本问题的约束条件下，当该值表示为两个互质整数 $P$ 和 $Q$ 的形式 $\frac{P}{Q}$ 时，我们可以证明存在一个唯一的整数 $R$，使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R < 998244353$。找出这样的 $R$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a grid with $H$ rows and $W$ columns.

We choose $K$ cells in this grid uniformly at random. The score is the number of cells in the minimum rectangle (whose edges are parallel to the axes of the grid) that contains all of the chosen cells.

Find the expected score modulo $998244353$.

What is rational number modulo $998244353$? We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as $\frac{P}{Q}$ by two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find such $R$.

Constraints

• $1\leq H,W \leq 1000$
• $1\leq K \leq HW$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $K$

Output

Print the answer.

Sample Input 1

2 2 2

Sample Output 1

665496238

The score equals $4$ in the following two cases: if cells $(1,1)$ and $(2,2)$ are chosen, or cells $(1,2)$ and $(2,1)$ are chosen. The other four cases yield a score of $2$.

Thus, the expected score equals $\frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}$. Since $665496238 \times 3 \equiv 8\pmod{998244353}$, you should print $665496238$.

Sample Input 2

10 10 1

Sample Output 2

1

Sample Input 3

314 159 2653

Sample Output 3

639716353

update @ 2024/3/10 12:20:55