题目描述
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.
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.
输入
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.
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.
输出
For each test case, output an integer representing the answer.
样例输入 Copy
1
11 2 1
样例输出 Copy
1024