공통 1비트 학번 배정

시간 제한5초메모리 제한1024 MB

요약

1부터 m까지의 서로 다른 정수 n개를 골라 AND 값의 1인 비트가 k개 이상이 되는 경우의 수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

학년이 시작될 때 International College of Paper Cutters(ICPC)의 학생들이 학번을 고른다. 학생은 $m$ 이하의 양의 정수를 하나씩 고를 수 있지만, 두 학생이 같은 학번을 고를 수는 없다.

학생들은 학번끼리 공통점을 가지기를 원한다. 구체적으로, 고른 모든 학번의 비트 AND에서 1인 비트가 적어도 $k$ 개 있어야 한다. 이렇게 고르는 방법의 수를 구하는 프로그램을 작성하라. 학생 중 한 명이라도 학번이 다르면 두 배정은 다른 것으로 본다.

두 정수 $a$ 와 $b$ 의 비트 AND는 $i$ 번째 비트가 $a$ 와 $b$ 에서 모두 1일 때에만 1인 정수 $c$ 이다. C, C++, Java, Python에서는 \& 연산자로 계산한다. 이 정의는 집합으로도 확장되며, 집합 $S$ 의 AND에서 $i$ 번째 비트는 $S$ 의 모든 원소에서 $i$ 번째 비트가 1일 때에만 1이다.

입력

첫 줄에 정수 세 개 $n$ ( $1 \leq n \leq 5 \times 10^5$ ), $k$ ( $1 \leq k \leq 5 \times 10^5$ ), $m$ ( $n \leq m \leq 5 \times 10^6$ )이 주어진다. $n$ 은 학생 수, $k$ 는 필요한 공통 1비트의 최소 개수, $m$ 은 학번이 가질 수 있는 최댓값이다.

출력

$[1, m]$ 에서 서로 다른 학번 $n$ 개를 고르는 방법 중, 고른 학번들의 비트 AND에서 1인 비트가 적어도 $k$ 개인 경우의 수를 출력하라. 답이 클 수 있으므로 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
2 2 10
```
예상 출력
```
6
```
예제 2
입력
```
3 4 14
```
예상 출력
```
0
```
예제 3
입력
```
2 1 100000
```
예상 출력
```
910073387
```