Mori got tired of living in Brazil and moved directly to Kazakhstan in search of a better life. In Kazakhstan, being a programmer is a thing of the past, and the new trendy profession at the moment is being a lumberjack. Since Mori is no fool, he decided to live the life of a lumberjack in Kazakhstan too!
Mori's new job as a lumberjack requires him to chop down $$$M$$$ trees distributed among the integer points $$$1$$$ to $$$N$$$. As everything is harmonious in the 2D world, all trees have height $$$H$$$ and have their roots on the $$$x$$$-axis, that is, $$$y=0$$$. There are no two trees at the same point.
When Mori chops down a tree located at point $$$a_i$$$, he can choose to fell it to the left, affecting the points $$$x$$$ such that $$$a_i-H \le x \le a_i$$$, or to the right, affecting the points $$$x$$$ such that $$$a_i \le x \le a_i+H$$$. If there are other trees in the affected range, this will trigger a series of chain reactions, knocking down those trees in the same direction as the original tree was felled. After all the trees resulting from chopping down the tree at point $$$a_i$$$ have been felled, Mori removes these trees and continues the process of chopping down trees with the remaining ones.
Mori faces a hindrance while performing his job. His contractor does not own the land corresponding to points $$$0$$$ and $$$N+1$$$. Therefore, during his work, he cannot chop down any trees at these two points.
Since Mori does not yet know where the $$$M$$$ trees are located, he wants to know the probability of being able to complete his work without chopping down trees at points $$$0$$$ and $$$N+1$$$, given that every configuration of $$$M$$$ trees scattered across $$$N$$$ points is equally likely. Print the answer modulo $$$998244353$$$.
Each test consists of multiple test cases. The first line of input contains a single integer $$$t (1 \le t \le 10^4)$$$ — the number of test cases. Then follows the descriptions of the test cases.
Each test case contains a single line of input containing three integers $$$N,M,H (1 \le N,H \le 10^5, 1 \le M \le N)$$$, representing respectively the number of points where the trees can be located, the number of trees, and the height of the trees.
It is guaranteed that the sum of $$$N$$$ over all test cases is less than or equal to $$$10^5$$$.
For each test case, print a single integer — the probability that Mori can complete his work modulo $$$998244353$$$.
Formally, the probability can be expressed as an irreducible fraction $$$\frac{x}{y}$$$. You should print the value $$$x \times y^{-1} \text{ mod } 998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$y \times y^{-1} \text{ mod } 998244353 = 1$$$.
52 1 12 1 24 2 22 2 255555 44444 333
1 0 499122177 0 250691060
| 2024 USP Try-outs |
|---|
| Finished |
