AT_abc297_f [ABC297F] Minimum Bounding Box 2

[problemUrl]: https://atcoder.jp/contests/abc297/tasks/abc297_f 縦 $ H $ 行、横 $ W $ 列のグリッドがあります。 このグリッドから一様ランダムに $ K $ 個のマスを選びます。選んだマスを全て含むような（グリッドの軸に辺が平行な）最小の長方形に含まれるマスの個数がスコアとなります。 得られるスコアの期待値を $ \text{mod\ }998244353 $ で求めてください。 有理数 $ \text{mod\ }998244353 $ とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、$ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。

N/A

N/A

### 制約 - $ 1\leq\ H,W\ \leq\ 1000 $ - $ 1\leq\ K\ \leq\ HW $ - 入力はすべて整数 ### Sample Explanation 1 マス $ (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 $ が答えとなります。