ユキは色鉛筆が大好きです。大好きな色鉛筆の芯が折れないように、ユキはそれぞれの色鉛筆の先にキャップを１つ装着します。いま、$N$色で１セットの色鉛筆セットがあります。また、$N$色のキャップがそれぞれ$M$個あります。すべてのキャップは１つの袋にまとめて入っています。
ユキさんの前には、どの色鉛筆にもキャップが装着されていない色鉛筆セットがあります。これから、以下の操作を繰り返して色鉛筆にキャップを装着します。
$T$回操作した後に、すべての色鉛筆にキャップが装着された状態になる可能性を計算してください。
色鉛筆の種類の数$N$と、キャップのセットの個数$M$と、操作の回数$T$が与えられる。上の操作を$T$回行った際に、すべての色鉛筆にキャップが装着されている確率を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$ $M$ $T$
１行に色鉛筆の種類の数$N$、キャップのセットの個数$M$、操作を行う回数$T$が正の整数で与えられる。ただし、$1 < M \times N < 998,244,353$、$1 \leq T \times N \leq 100,000$を満たす。また、$T \leq M \times N$である。
すべての色鉛筆にキャップが装着された状態になる確率を既約分数$\frac{p}{q}$で表したとき、$qx \equiv p (\mod 998,244,353)$を満たすような$x$の値を出力せよ。ただし、$a \equiv b (\mod c)$ ($a,b$は非負整数、$c$は正の整数)とは、$a$を$c$で割ったあまりと$b$を$c$で割ったあまりが等しいという意味である。
※補足：この問題で求める確率は必ず有理数になる。また、この問題の制約下では、求める確率を既約分数 $\frac{p}{q}$で表したときに$q$は$998,244,353$で割り切れない。このとき、$qx \equiv p (\mod 998,244,353)$を満たすような$0$以上$998,244,353$未満の整数$x$はただ一つしか存在しない。
2 10 11
1
3 4 3
871195072