Problem Description

Given $n, k, p$, find the number of ordered $p$-tuples $(a_1, a_2, \cdots, a_p)$ that satisfy:

• $\forall i \in [1, p]$, $a_i \in [1, n]$.
• $\forall i \in [1, p-1]$, $\operatorname{popcount}(a_i \oplus a_{i+1}) = k$.
• $\forall i, j \in [1, p], i \neq j$, $a_i \neq a_j$.

The answer should be taken modulo $998244353$.

• $\operatorname{popcount}(x)$ denotes the number of $1$s in the binary representation of $x$.
• $\oplus$ denotes the bitwise XOR operation.
• Two ordered $p$-tuples $(a_1, a_2, \dots, a_p)$ and $(b_1, b_2, \dots, b_p)$ are considered different if and only if there exists an $i \in [1, p]$ such that $a_i \neq b_i$.

Input Format

A single line containing three positive integers $n, k, p$.

Output Format

A single line containing one number, representing the answer.

Sample Input and Output

Input Sample #1

5 1 2

Output Sample #1

8

Input Sample #2

6 1 3

Output Sample #2

12

Input Sample #3

7 1 4

Output Sample #3

48

Input Sample #4

8 3 5

Output Sample #4

6

Input Sample #5

9 2 5

Output Sample #5

72

Input Sample #6

114 3 3

Output Sample #6

106624

Input Sample #7

514 3 4

Output Sample #7

296097032

Input Sample #8

1000 7 5

Output Sample #8

569405945

Input Sample #9

1000 7 1

Output Sample #9

1000

Notes

For all test cases, it is guaranteed that $1 \leq n \leq 1000$, $1 \leq k \leq \lfloor \log_2 n \rfloor$, and $1 \leq p \leq 5$.

The specific constraints for each test point are as follows:

见题面 Input 部分

见题面 Output 部分