#P1967E1. Again Counting Arrays (Easy Version)

    ID: 10617 Type: RemoteJudge 5000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 10 Uploaded By: Tags>combinatoricsdpfftmath*3100

Again Counting Arrays (Easy Version)

Description

This is the easy version of the problem. The differences between the two versions are the constraints on n,m,b0n, m, b_0 and the time limit. You can make hacks only if both versions are solved.

Little R has counted many sets before, and now she decides to count arrays.

Little R thinks an array b0,,bnb_0, \ldots, b_n consisting of non-negative integers is continuous if and only if, for each ii such that 1in1 \leq i \leq n, bibi1=1\lvert b_i - b_{i-1} \rvert = 1 is satisfied. She likes continuity, so she only wants to generate continuous arrays.

If Little R is given b0b_0 and a1,,ana_1, \ldots, a_n, she will try to generate a non-negative continuous array bb, which has no similarity with aa. More formally, for all 1in1 \leq i \leq n, aibia_i \neq b_i holds.

However, Little R does not have any array aa. Instead, she gives you nn, mm and b0b_0. She wants to count the different integer arrays a1,,ana_1, \ldots, a_n satisfying:

  • 1aim1 \leq a_i \leq m;
  • At least one non-negative continuous array b0,,bnb_0, \ldots, b_n can be generated.

Note that bi0b_i \geq 0, but the bib_i can be arbitrarily large.

Since the actual answer may be enormous, please just tell her the answer modulo 998244353998\,244\,353.

Each test contains multiple test cases. The first line contains the number of test cases t (1t104)t\ (1 \leq t \leq 10^4). The description of the test cases follows.

The first and only line of each test case contains three integers nn, mm, and b0b_0 (1n21051 \leq n \leq 2 \cdot 10^5, 1m21051 \leq m \leq 2 \cdot 10^5, 0b021050 \leq b_0 \leq 2\cdot 10^5) — the length of the array a1,,ana_1, \ldots, a_n, the maximum possible element in a1,,ana_1, \ldots, a_n, and the initial element of the array b0,,bnb_0, \ldots, b_n.

It is guaranteed that the sum of nn over all test cases does not exceeds 21052\cdot 10^5.

For each test case, output a single line containing an integer: the number of different arrays a1,,ana_1, \ldots, a_n satisfying the conditions, modulo 998244353998\,244\,353.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t104)t\ (1 \leq t \leq 10^4). The description of the test cases follows.

The first and only line of each test case contains three integers nn, mm, and b0b_0 (1n21051 \leq n \leq 2 \cdot 10^5, 1m21051 \leq m \leq 2 \cdot 10^5, 0b021050 \leq b_0 \leq 2\cdot 10^5) — the length of the array a1,,ana_1, \ldots, a_n, the maximum possible element in a1,,ana_1, \ldots, a_n, and the initial element of the array b0,,bnb_0, \ldots, b_n.

It is guaranteed that the sum of nn over all test cases does not exceeds 21052\cdot 10^5.

Output

For each test case, output a single line containing an integer: the number of different arrays a1,,ana_1, \ldots, a_n satisfying the conditions, modulo 998244353998\,244\,353.

Sample Input 1

6
3 2 1
5 5 3
13 4 1
100 6 7
100 11 3
1000 424 132

Sample Output 1

6
3120
59982228
943484039
644081522
501350342

Note

In the first test case, for example, when a=[1,2,1]a = [1, 2, 1], we can set b=[1,0,1,0]b = [1, 0, 1, 0]. When a=[1,1,2]a = [1, 1, 2], we can set b=[1,2,3,4]b = [1, 2, 3, 4]. In total, there are 66 valid choices of a1,,ana_1, \ldots, a_n: in fact, it can be proved that only a=[2,1,1]a = [2, 1, 1] and a=[2,1,2]a = [2, 1, 2] make it impossible to construct a non-negative continuous b0,,bnb_0, \ldots, b_n, so the answer is 232=62^3 - 2 = 6.