408472: GYM103145 G Ball

There are $$$n$$$ grooves distributed on a slope evenly. We index the highest groove with $$$n$$$, while the lowest is $$$1$$$. If we choose a number $$$i$$$, let a ball fall freely over the $$$i$$$th groove, three different situations may happen. If the $$$i$$$th groove is empty, then the ball will occupy it. If the $$$i$$$th groove is already occupied, the ball will roll down and occupy the first empty groove. If all the grooves below the $$$i$$$th groove are occupied, the ball will fall out of the slope.

Now Lucida has $$$m$$$ balls. He wondered how many different ways for him to throw these balls such that there are exactly $$$k$$$ of them falling out of the slope.

A way to throw these m balls can be represented by a sequence p($$$\{p_1,p_2,...,p_n\}$$$, $$$1\leq p_i\leq n$$$). $$$p_i$$$ means that the $$$i$$$th ball is fall freely over the $$$p_i$$$ groove.

Two ways are considered the same if the sequence $$$p$$$ is the same.

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1\leq T \leq 1000$$$) indicating the number of test cases.

The following $$$T$$$ lines each contains three integers $$$n, m, k$$$ ($$$1 \leq n\leq 500$$$,$$$1\leq m\leq 1000$$$, $$$0\leq k\leq 500$$$, $$$k < m \leq n + k$$$), the number of grooves, the number of balls and the number of balls which fall out of the slope.

For each test case, output one line contains one integer indicating the answer.

Since the answer can be very large, you only need to output the answer modulo $$$998244353$$$.

1
3 2 0

8

For the sample, there are $$$3$$$ grooves in total. We throw two balls and none of them falls out of the slope. There are $$$9$$$ different ways to throw the balls and the only way that causes one of them to fall is to throw both of them over the first groove. So the answer will be $$$9-1=8$$$.