题目描述

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

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

找出得分对 $998244353$ 取模后的期望值。

什么是对 $998244353$ 取模的有理数？我们可以证明所求的期望值总是一个有理数。此外，在问题的约束条件下，当将该值表示为两个互质整数 $P$ 和 $Q$ 的形式 $\\frac{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