最小边界矩形 2

题目描述

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

我们从这个网格中等概率随机地选择 $K$ 个格子。得分是包含所有被选格子的最小矩形（矩形的边与网格的坐标轴平行）中的格子数。

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

什么是模 $998244353$ 的有理数？

可以证明所求期望值总是有理数。 此外，在本题的约束下，当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，可以证明存在唯一的整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \le R \lt 998244353$。求出这样的 $R$。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$ $K$

输出格式

输出答案。

样例

2 2 2

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$。

10 10 1

1

314 159 2653

639716353

数据范围

• $1 \le H,W \le 1000$
• $1 \le K \le HW$
• 输入中的所有值均为整数。