AT_abc297_f.[ABC297F] Minimum Bounding Box 2

有一个高 $H$ 行、宽 $W$ 列的网格。

从这个网格中等概率随机选择 $K$ 个格子。将所有被选中的格子包含在内的、边与网格轴平行的最小矩形中，包含的格子数作为得分。

请你求出最终得分的期望值，并对 $998244353$ 取模。

有理数 $\bmod\ 998244353$ 的含义如下：可以证明，所求的期望值一定是有理数。在本题的约束下，设该值可以表示为互质的两个整数 $P$、$Q$，即 $\frac{P}{Q}$。请你输出唯一满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R<998244353$ 的整数 $R$。

输入从标准输入读入，格式如下：

$H$ $W$ $K$

输出答案。

约束条件

• $1\leq H,W\leq 1000$
• $1\leq K\leq HW$
• 输入均为整数

样例解释 1

如果选择了格子 $(1,1)$ 和 $(2,2)$，或者选择了格子 $(1,2)$ 和 $(2,1)$，这两种情况下得分为 $4$。除此之外的 $4$ 种情况得分为 $2$。因此，期望得分为 $\frac{4\times 2 + 2\times 4}{6} = \frac{8}{3}$，而 $665496238\times 3\equiv 8\pmod{998244353}$，所以答案为 $665496238$。

由 ChatGPT 4.1 翻译