Distinct Ordered Tuples Path Count

Given three integers n, k, and p, count the number of ordered p-tuples \((a_1,a_2,\dots,a_p)\) that satisfy the following conditions:

• For every \(i\) with \(1 \le i \le p\), \(a_i \in [1,n]\).
• For every \(i\) with \(1 \le i < p\), \(\operatorname{popcount}(a_i \oplus a_{i+1}) = k\), where \(\operatorname{popcount}(x)\) denotes the number of ones in the binary representation of \(x\) and \(\oplus\) denotes the bitwise XOR operation.
• All elements in the tuple are distinct; that is, \(a_i \neq a_j\) for every \(i \neq j\).

Output the answer modulo \(998244353\).

inputFormat

The input consists of a single line containing three integers n, k, and p separated by spaces.

outputFormat

Output a single integer representing the number of valid ordered p-tuples modulo \(998244353\).

sample

4 1 2

4