题目背景

我用烟花宣告，用挥手告别，用鞠躬感谢，过去的都已经过去，接下来的路我要悠闲地走，愉悦地走，脚步如同时间不会停止，下一年，我们还会再会。

题目描述

这次的题目背景和 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$。

输出格式

一行一个数，表示答案。

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

提示

对于所有测试数据，保证 $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$		$2$
$4 \sim 5$	$300$	$3$
$6 \sim 12$	$1000$
$13 \sim 15$		$4$
$16 \sim 21$	$300$	$5$
$22 \sim 25$	$1000$