Codeforces Round 942 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E2. Again Counting Arrays (Hard Version)

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThis is the hard version of the problem. The differences between the two versions are the constraints on $$$n, 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 $$$b_0, \ldots, b_n$$$ consisting of non-negative integers is continuous if and only if, for each $$$i$$$ such that $$$1 \leq i \leq n$$$, $$$\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 $$$b_0$$$ and $$$a_1, \ldots, a_n$$$, she will try to generate a non-negative continuous array $$$b$$$, which has no similarity with $$$a$$$. More formally, for all $$$1 \leq i \leq n$$$, $$$a_i \neq b_i$$$ holds.

However, Little R does not have any array $$$a$$$. Instead, she gives you $$$n$$$, $$$m$$$ and $$$b_0$$$. She wants to count the different integer arrays $$$a_1, \ldots, a_n$$$ satisfying:

- $$$1 \leq a_i \leq m$$$;
- At least one non-negative continuous array $$$b_0, \ldots, b_n$$$ can be generated.

Note that $$$b_i \geq 0$$$, but the $$$b_i$$$ can be arbitrarily large.

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

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$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 $$$n$$$, $$$m$$$, and $$$b_0$$$ ($$$1 \leq n \leq 2 \cdot 10^6$$$, $$$1 \leq m \leq 2 \cdot 10^6$$$, $$$0 \leq b_0 \leq 2\cdot 10^6$$$) — the length of the array $$$a_1, \ldots, a_n$$$, the maximum possible element in $$$a_1, \ldots, a_n$$$, and the initial element of the array $$$b_0, \ldots, b_n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceeds $$$10^7$$$.

Output

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

Example

Input

63 2 15 5 313 4 1100 6 7100 11 31000 424 132

Output

6 3120 59982228 943484039 644081522 501350342

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 21:35:11 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|