在学年开始时，国际剪纸学院（ICPC）的学生们需要选择他们的学生 ID。学生们可以选择任何小于或等于某个最大值的正整数作为他们的 ID，但没有两名学生可以选择相同的学生 ID。

经过一番商议，学生们决定在他们所有的 ID 之间寻找一些共同点。具体来说，他们希望选择 ID，使得所有学生 ID 的按位与（bitwise AND）结果至少包含 $k$ 个 1-bit。ICPC 的学生们请求你编写一个程序来计算实现这一目标的方案数。如果两种分配方案中至少有一名学生的 ID 不同，则视为不同的分配方案。

两个整数 $a$ 和 $b$ 的按位与是一个整数 $c$，其二进制表示如下：$c$ 的第 $i$ 位为 1 当且仅当 $a$ 和 $b$ 的第 $i$ 位均为 1。C、C++、Java 和 Python 都支持使用 & 运算符计算两个整数的按位与。

这个定义可以推广到数字集合。整数集合 $S$ 的按位与是一个整数 $c$，其二进制表示如下：$c$ 的第 $i$ 位为 1 当且仅当 $S$ 中每个元素的第 $i$ 位均为 1。

输入格式

输入包含一行，包含三个整数 $n$ ($1 \le n \le 5 \times 10^5$)，$k$ ($1 \le k \le 5 \times 10^5$) 和 $m$ ($n \le m \le 5 \times 10^6$)，其中 $n$ 是学生人数，$k$ 是要求的共同位（1-bit）的最小数量，$m$ 是学生 ID 的最大允许值。

输出格式

输出一个整数，表示从范围 $[1, m]$ 中选择 $n$ 个不同的学生 ID，使得这些学生 ID 的按位与结果中 1-bit 的数量至少为 $k$ 的方案数。由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

说明

有 2 名学生，他们希望其学生 ID 的按位与结果至少有 2 个 1-bit，且最大允许的学生 ID 为 10。有效的 ID 分配方案为 $\{(3, 7), (5, 7), (6, 7), (7, 3), (7, 5), (7, 6)\}$。

样例

样例输入 1

2 2 10

样例输出 1

6

样例输入 2

3 4 14

样例输出 2

0

样例输入 3

2 1 100000

样例输出 3

910073387