Again Counting Arrays (Easy Version)
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 3100
Tags: combinatorics, dp, fft, math

This is the easy 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 format:
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^5$$$, $$$1 \leq m \leq 2 \cdot 10^5$$$, $$$0 \leq b_0 \leq 2\cdot 10^5$$$) — 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 $$$2\cdot 10^5$$$.

Output format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

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$$$.

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

Example output:
6
3120
59982228
943484039
644081522
501350342

Editorial:
It can be easily proven that for a given $$$a$$$, we can always try to get the largest $$$b_i$$$ from $$$1$$$ to $$$n$$$ one by one. A perceptual understanding is that if not so, we can't escape from some gap in $$$a$$$ either.
Thus, it's easy to get a $$$\mathcal O(nm)$$$ solution: Let $$$dp_{i,j}$$$ be, in the optimal $$$b$$$ determination progress, the ways of $$$b_i = j$$$. The transition is easy, and it reminds us that $$$b_{i, m}$$$s always add to answers with $$$m^{n-i}$$$ straightly without continuing to transmit.
There is a $$$\mathcal O(n\log^2 n)$$$ solution that solves the above grid path counting problem with NTT. It can pass this version of the problem, but it is not that useful for the hard version.
However, we strongly suggest you read the following part as it reveals the $$$\mathcal O(n)$$$ solution in the hard version. It currently works in $$$\mathcal O(n\sqrt{n})$$$, but in fact, it runs much faster than the polylog one.
Try to modify the solution so that it works in $$$\mathcal O(\frac{n^2}{m})$$$.
Consider the simplified version: You have two lines $$$y = x + b_1$$$ and $$$y = x + b_2$$$ in a Cartesian coordinate system. You are at $$$(0, 0)$$$ and you want to move to $$$(p, q)$$$. Each move is $$$x \gets x + 1$$$ or $$$y \gets y + 1$$$. You are not allowed to get onto the points on the two lines. Count the number of ways to get to $$$(p, q)$$$.
We will introduce a classical $$$\mathcal O(\frac{p+q}{|b_2 - b_1|})$$$ solution$$$^\dagger$$$.
Then, for each invalid path, we enumerate the end position where $$$b_i = 0, a_{i+1} = 1$$$, and after that, simply conduct the $$$\mathcal O(\frac nm)$$$ process (you just need to change some parameters).
Now, we get a $$$\mathcal O(n\sqrt{n})$$$ solution, which should be fast enough to pass.
Note
$$$^\dagger$$$: If there is only one line $$$y = x + b$$$, we can do like what we have done in solving the grid path counting problem, which ultimately yields one of the general term formulas for Catalan numbers.
Remind that the key part is to flip $$$(p, q)$$$ by the line $$$y = x + b$$$ to $$$(p', q')$$$. Thus, for each invalid path (It touches at least once $$$y = x + b$$$), if we flip all the way from the last time it touches the line to $$$(p, q)$$$, then it uniquely corresponds to a path starting from the origin, and finally arriving at $$$(p', q')$$$.
For the answer to the problem with two lines $$$y_1 = x + b_1$$$, $$$y_2 = x + b_2$$$, we perform the inclusion-exclusion principle (aka. the reflection method). Let's denote $$$\tt A$$$ as touching $$$y_1$$$, $$$\tt B$$$ as touching $$$y_2$$$.
An invalid path can, for example, be explained as $$$S = \tt AAABBABAABBBA$$$. From the experiment in solving the previous problem, we shrink $$$S$$$ into $$$\tt ABABABA$$$ (That is, to replace each $$$\tt AA$$$ with $$$\tt A$$$, and each $$$\tt BB$$$ with $$$\tt B$$$).
Then we can calculate the answer as, $$$f(\varnothing) - f(\texttt{A}) - f(\texttt{B}) + f(\texttt{AB}) + f(\texttt{BA}) - f(\texttt{ABA}) - f(\texttt{BAB}) + \ldots$$$. $$$f(S)$$$ refers to flip $$$(p, q)$$$ by the characters in $$$S$$$ in order. For example, $$$f(\texttt{ABA})$$$ is, flip $$$(p, q)$$$ by first $$$y_1$$$, then $$$y_2$$$, then $$$y_1$$$ again, and count the paths from the origin to $$$(p^\star, q^\star)$$$. And $$$f(S)$$$ actually refers to all the invalid schemes containing the pattern $$$S$$$ which are the borderlines a path touches in order.
There are $$$\mathcal O(\frac{p+q}{\lvert b_1 - b_2 \rvert})$$$ non-zero terms, each term is a combinatorial number. So the overall time complexity is $$$\mathcal O(\frac{p+q}{\lvert b_1 - b_2 \rvert})$$$.