Count

Problem Description

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 $A_i$ be the $i$-th element of sequence $A$. For all positive integers $i$ not exceeding $k$, it is satisfied that $A_i = A_{n-k+i}$. Calculate the total number of such sequences $A$ that satisfy the conditions and output the result modulo 998244353.

Input

The first line contains an integer $T （T\leq 1000）$, representing the number of test cases. Each of the next $T$ lines contains three integers $n$, $m$, and $k（1 \leq n,m,k \leq 10^{18} , k \leq n）$, representing the parameters for one test case.

Output

For each test case, output an integer representing the answer.

Sample Input

1
11 2 1

Sample Output

1024

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）