9051: Snake

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.

The first line of the input contains an integer T (1 ≤ T ≤ 200), indicating the number of the test cases. The next T lines, each line has three integers n, m, k (1 ≤ m, k ≤ n ≤ 106 ), 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 Pn ≤ 108 .

T lines, each line has one interger, indicating the answer.

Note that the answer could be zero!