[DTOI 2023] D. Goodbye 2022
题目背景
> 我用烟花宣告，用挥手告别，用鞠躬感谢，过去的都已经过去，接下来的路我要悠闲地走，愉悦地走，脚步如同时间不会停止，下一年，我们还会再会。
题目描述
这次的题目背景和 luanmenglei 没有一点关系。
给定 $n,k,p$，求有多少有序 $p$ 元组 $(a_1,a_2,\cdots,a_p)$ 满足
- $\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$。
答案对 $998244353$ 取模。
---
- 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制表达下 $1$ 的个数。
- $\oplus$ 表示按位异或操作。
- 两个有序 $p$ 元组 $(a_1,a_2,\dots,a_p)$，$(b_1,b_2,\dots,b_p)$ 不同当且仅当存在 $i\in[1,p]$ 使得 $a_i\neq b_i$。
输入输出格式
输入格式
一行三个正整数 $n,k,p$。
输出格式
一行一个数，表示答案。
输入输出样例
输入样例 #1
5 1 2输出样例 #1
8输入样例 #2
6 1 3输出样例 #2
12输入样例 #3
7 1 4输出样例 #3
48输入样例 #4
8 3 5输出样例 #4
6输入样例 #5
9 2 5输出样例 #5
72输入样例 #6
114 3 3输出样例 #6
106624输入样例 #7
514 3 4输出样例 #7
296097032输入样例 #8
1000 7 5输出样例 #8
569405945输入样例 #9
1000 7 1输出样例 #9
1000说明
对于所有测试数据，保证 $1\leq n \leq 1000$，$1\leq k\leq \lfloor \log_2 n\rfloor$，$1 \leq p \leq 5$。
每个测试点的具体限制见下表：
| 测试点编号 | $n\leq$ | $p =$ |
| :-: | :-: |:-:|
| $1$ | $1000$ | $1$ |
| $2 \sim 3$ | $1000$ |$2$|
| $4 \sim 5$ | $300$ |$3$|
| $6 \sim 12$ | $1000$ |$3$|
| $13 \sim 15$ | $1000$ |$4$|
| $16 \sim 21$ | $300$ |$5$|
| $22 \sim 25$ | $1000$ |$5$|