시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB222100.000%

문제

At the beginning of the school year, the students in the International College of Paper Cutters (ICPC) choose their student IDs. The students can choose any positive integer less than or equal to some maximum number for their IDs, but no two students can choose the same student ID.

After some deliberation among the ranks, the students decided they wanted to find some common ground between all their IDs. In particular, they want to choose their IDs such that the bitwise AND of all of their student IDs has at least some minimum number of $1$-bits. The students of the ICPC are asking you to write a program to compute the number of ways to do this. Two assignments are different if there is at least one student that has a different student ID in each assignment.

The bitwise AND of two integers $a$ and $b$ is an integer $c$ whose binary representation is as follows: the $i$th bit of $c$ is $1$ if and only if the $i$th bits of both $a$ and $b$ are $1$. C, C++, Java, and Python all support computing the bitwise AND of two integers using the \& operator.

This definition generalizes to sets of numbers. The bitwise AND of a set of integers $S$ is an integer $c$ whose binary representation is as follows: the $i$th bit of $c$ is $1$ if and only if the $i$th bit of each element of $S$ is $1$.

입력

The single line of input contains three integers $n$ ($1\leq n \leq 5 \times 10^5$), $k$ ($1 \leq k \leq 5 \times 10^5$), and $m$ ($n \leq m \leq 5 \times 10^6$), where $n$ is the number of students, $k$ is the required minimum number of common bits, and $m$ is the maximum number any student ID could be.

출력

Output a single integer, which is the number of ways to choose $n$ distinct student IDs from the range $[1, m]$ such that the number of $1$-bits in the bitwise AND of the student IDs has at least $k$ $1$-bits. Since the answer may be large, output it modulo $998\,244\,353$.

예제 입력 1

2 2 10


예제 출력 1

6


There are $2$ students, they want the bitwise AND of their student IDs to have at least $2$ $1$-bits and the maximum allowed student ID is $10$. The valid ID assignments are $\{(3, 7), (5, 7), (6, 7), (7, 3), (7, 5), (7, 6)\}$.

예제 입력 2

3 4 14


예제 출력 2

0


예제 입력 3

2 1 100000


예제 출력 3

910073387


출처

• 문제를 만든 사람: Arnav Sastry