An integer sequence $V_1, V_2, \dots, V_N$ is called super decreasing if $V_N \ge 0$, and $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ for all $1 \le i < N$.
Given positive integers $N$ and $M$, find the number of pairs of integer sequences $A$ and $B$ of length $N$ such that $1 \le A_i, B_i \le M$ for all $1 \le i \le N$, and for all super decreasing sequences $V$ of length $N$,
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Since the number of such pairs can be very large, print the answer modulo $998\,244\,353$.
Input
The input is given in the following format:
T N M :
- All input values are integers.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $5000$.
- It is guaranteed that the sum of $M$ over all test cases does not exceed $5000$.
Output
For each test case, output a single integer — the number of pairs of sequences $(A, B)$ satisfying the conditions, modulo $998\,244\,353$.
Examples
Sample Input 1
4 1 1 2 2 2 1 34 43
Sample Output 1
1 10 1 711021868
Note
Test case 1: The only possible pair of sequences is $([1], [1])$, and it is valid.
Test case 2: The following are valid pairs of sequences:
- For $B = [1, 1]$, any choice of $A$ is valid. There are $4$ possible choices.
- For $B = [1, 2]$, valid choices of $A$ are $[1, 2], [2, 1], [2, 2]$.
- For $B = [2, 1]$, valid choices of $A$ are $[2, 1], [2, 2]$.
- For $B = [2, 2]$, the only valid choice of $A$ is $[2, 2]$.
So, the number of valid pairs of sequences equals $4 + 3 + 2 + 1 = 10$.