题目描述
There are $n$ snakes indexed from $1$ to $n$, each snake's length is $1$ at first.
There will be battles between the snakes, each battle can take place between any two alive snakes.
After each battle, the winner eat the loser, and merge their body. For instance, if snake 1 battles with snake 2 and win, it will eat snake 2 and become 1->2, otherwise it will be eaten and the other snake will become 2->1. For another example, if snake 3->2->7 battles with snake 5->6->4, the winner will become 3->2->7->5->6->4 or 5->6->4->3->2->7.
In addition, if a snake's length is **greater than** $k$ after a battle, it will become the king of the snakes!
A final state is defined by the set of alive snakes after battles. For instance, for $n=3$, all possible final states are {1,2,3},{1->2,3},{1->3,2},{2->1,3},{2->3,1},{3->1,2},{3->2,1},{1->2->3},{1->3->2},{2->1->3},{2->3->1},{3->1->2},{3->2->1}.
Now you know after battles, there are $m$ snakes alive and no king of the snake exist. Your task is to calculate the number of different possible final states modulo $998244353$
There will be battles between the snakes, each battle can take place between any two alive snakes.
After each battle, the winner eat the loser, and merge their body. For instance, if snake 1 battles with snake 2 and win, it will eat snake 2 and become 1->2, otherwise it will be eaten and the other snake will become 2->1. For another example, if snake 3->2->7 battles with snake 5->6->4, the winner will become 3->2->7->5->6->4 or 5->6->4->3->2->7.
In addition, if a snake's length is **greater than** $k$ after a battle, it will become the king of the snakes!
A final state is defined by the set of alive snakes after battles. For instance, for $n=3$, all possible final states are {1,2,3},{1->2,3},{1->3,2},{2->1,3},{2->3,1},{3->1,2},{3->2,1},{1->2->3},{1->3->2},{2->1->3},{2->3->1},{3->1->2},{3->2->1}.
Now you know after battles, there are $m$ snakes alive and no king of the snake exist. Your task is to calculate the number of different possible final states modulo $998244353$
输入
The first line of the input contains an integer $T\ (1\le T\le 200)$, indicating the number of the test cases.
The next $T$ lines, each line has three integers $n, m, k\ (1\le m,k \le n \le 10^6)$, indicating the number of snakes at first, the number of snakes after battles and the body length that need to be surpassed to become the king of the snake.
It's guaranteed that $\sum n\le 10^8$.
The next $T$ lines, each line has three integers $n, m, k\ (1\le m,k \le n \le 10^6)$, indicating the number of snakes at first, the number of snakes after battles and the body length that need to be surpassed to become the king of the snake.
It's guaranteed that $\sum n\le 10^8$.
输出
$T$ lines, each line has one interger, indicating the answer
样例输入 Copy
7
3 3 3
3 2 3
3 1 3
6 2 3
6 2 4
6 2 5
1000000 114514 233
样例输出 Copy
1
6
6
360
1080
1800
920789612
提示
**Note that the answer could be zero!**