For some integers ~N, K, M~, define the "caterpillar sum" to be the following sum:

$$\displaystyle \mathrm{Caterpillar}(N, K, M) = \sum_{x=K \times M}^N x(x-M)(x-2M)...(x-(K-1)M) $$

For example, the caterpillar sum for ~N = 5, K = 3, M = 1~ is ~3\times 2\times 1 + 4\times 3\times 2 + 5\times 4\times 3 = 90~.

Your task is to evaluate the caterpillar sum for various values of ~N, K~, and ~M~.

Input Specification

The input begins with an integer ~T~ ~(1 \le T \le 10^4)~, the number of test cases. ~T~ lines follow, each containing three integers ~N, K, M~ ~(1 \le N \le 10^9, 1 \le K \le 100, 1 \le M \le 10^6, K\times M \le N)~.

For at least 30 points, ~K \le 3~ and ~M = 1~.

Output Specification

For each test case, output the caterpillar sum of ~N, K, M~, modulo ~998244353~.

Sample Input 1

3
5 3 1
10 1 1
10 10 1

Sample Output 1

90
55
3628800