Background

I announce with fireworks, say goodbye with a wave, and give thanks with a bow. Everything in the past is already past. From now on, I will walk the road ahead in a relaxed way, in a happy way. My steps are like time that never stops. Next year, we will meet again.

Problem Description

This problem background has nothing to do with luanmenglei.

Given $n, k, p$, find how many ordered $p$-tuples $(a_1, a_2, \cdots, a_p)$ satisfy:

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

Output the answer modulo $998244353$.

• $\operatorname{popcount}(x)$ denotes the number of $1$ bits 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 different if and only if there exists $i \in [1, p]$ such that $a_i \neq b_i$.

Input Format

One line with three positive integers $n, k, p$.

Output Format

One line with one integer, representing the answer.

5 1 2

8

6 1 3

12

7 1 4

48

8 3 5

6

9 2 5

72

114 3 3

106624

514 3 4

296097032

1000 7 5

569405945

1000 7 1

1000

Hint

For all testdata, 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 limits for each test point are shown in the table below:

Translated by ChatGPT 5