配点 : $500$ 点

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。

このグリッドから一様ランダムに $K$ 個のマスを選びます。選んだマスを全て含むような（グリッドの軸に辺が平行な）最小の長方形に含まれるマスの個数がスコアとなります。

得られるスコアの期待値を $\text{mod }998244353$ で求めてください。

制約

• $1\leq H,W \leq 1000$
• $1\leq K \leq HW$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $K$

出力

答えを出力せよ。

2 2 2

665496238

マス $(1,1)$ とマス $(2,2)$ が選ばれた場合、またはマス $(1,2)$ とマス $(2,1)$ が選ばれた場合の $2$ 通りではスコアは $4$ となります。また、それ以外の $4$ 通りではスコアは $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