問題文

椎葉さんと因幡さんが、要素数が $2N$ で $1$ 以上 $M$ 以下の整数からなる整数列 $A=(a_1,a_2,\ldots,a_{2N})$ と 空の整数列 $B$ を用いてゲームをします。

椎葉さんが先手で、 $A$ が空になるまで交互に以下の操作を繰り返します。

• $A$ の要素を $1$ つ選び、 $A$ から削除し、$B$ の末尾に加える。

$A$ が空になったときの $B$ の要素数は $2N$ ですが、これを $B=(b_1,b_2,\ldots,b_{2N})$ としたとき、ある整数 $j$ $(1 \leq j \leq 2N-1)$ が存在して $|b_j-b_{j+1}| \geq K$ が成立するならば後手の因幡さんの勝ちで、そうでないなら先手の椎葉さんの勝ちです。

整数列 $A$ として考えられるものは全部で $M^{2N}$ 通りありますが、そのうち両者が最適にゲームを進めたとき、先手の椎葉さんが勝つようなものは全部で何通りありますか？

答えを $998244353$ で割った余りを求めてください。

入力

$N \ M \ K$

• $1\le N,M,K\le 10^{18}$
• 入力はすべて整数

出力

答えを $998244353$ で割った余りを出力してください。

サンプル

2 2 1

2

3 3 3

729

178096 418269 13333

111203503

1000 1000000000000 998244853

662474981