问题 A: Count

You are given three positive integers $n$, $m$, and $k$.

Your task is to calculate the total number of sequences $A$ of length $n$ that satisfy the following conditions:

1. All elements of $A$ are integers from $1$ to $m$（inclusive）.
   
2. Let Ai be the $i$-th element of sequence $A$. For all positive integers $i$ not exceeding $k$, it is satisfied thatAi=An−k+i.
   

Calculate the total number of such sequences $A$ that satisfy the conditions and output the result modulo 998244353.

The first line contains an integer $T（T\le 1000）$, representing the number of test cases.

Each of the next $T$ lines contains three integers $n$, $m$, and k（1≤n,m,k≤1018,k≤n）, representing the parameters for one test case.