Problem Statement

Shiiba and Inaba play a game using an integer sequence $A=(a_1,a_2,\ldots,a_{2N})$ with $2N$ elements, each an integer between $1$ and $M$, inclusive, and an empty integer sequence $B$.

Shiiba goes first, and they alternately repeat the following operation until $A$ becomes empty.

• Choose $1$ element of $A$, remove it from $A$, and append it to the end of $B$.

When $A$ becomes empty, $B$ has $2N$ elements. Writing it as $B=(b_1,b_2,\ldots,b_{2N})$, if there exists an integer $j$ $(1 \leq j \leq 2N-1)$ such that $|b_j-b_{j+1}| \geq K$ holds, the second player Inaba wins; otherwise, the first player Shiiba wins.

There are $M^{2N}$ possible integer sequences $A$ in total. Among them, how many are such that the first player Shiiba wins when both players play optimally?

Find the answer modulo $998244353$.

Input

$N \ M \ K$

• $1\le N,M,K\le 10^{18}$
• All input values are integers.

Output

Output the answer modulo $998244353$.

Sample

2 2 1

2

3 3 3

729

178096 418269 13333

111203503

1000 1000000000000 998244853

662474981