기계 학습

시간 제한2초메모리 제한512 MB

요약

값이 0부터 k까지인 길이 n의 배열 중, 뒤의 값이 앞의 값의 모든 1비트를 포함하고 주어진 위치 쌍의 값이 서로 달라야 하는 배열의 수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

인공지능 연구실에서 새로운 기계 학습 방법을 개발했다. 학습에는 $n$ 번의 반복이 있고, 각 반복에서 학습 프로그램을 하나의 학습 데이터 세트로 실행한다.

복잡도가 0부터 $k$ 까지인 학습 데이터 세트가 준비되어 있다. 학습 계획은 배열 $[a_1, a_2, \ldots, a_n]$ 로 표현하며, $a_i$ 는 $i$ 번째 반복에서 사용하는 데이터 세트의 복잡도이다. 모든 $i$ ( $1 \le i \le n$ )에 대해 $0 \le a_i \le k$ 를 만족해야 한다.

계획의 효율은 복잡도의 이진 표현에 따라 정해진다. $1 \le i < j \le n$ 인 모든 $i$ , $j$ 에 대해 $(a_i \,\&\, a_j) = a_i$ 가 성립하면 계획이 효율적이다. 여기서 $\&$ 는 비트 AND 연산이다. 예를 들어 $(14 \,\&\, 7) = (1110_2 \,\&\, 0111_2) = 110_2 = 6$ 이다.

같은 복잡도의 데이터 세트만 반복해서 쓰면 학습이 진전되지 않는다. 그래서 $m$ 개의 요구 조건이 주어진다. 각 조건은 두 수 $l_i$ , $r_i$ 로 주어지며 $a_{l_i} \ne a_{r_i}$ 를 뜻한다.

모든 요구 조건을 만족하는 효율적인 학습 계획의 개수를 구하라. 답은 $10^9 + 7$ 로 나눈 나머지로 출력한다.

입력

첫 줄에 세 정수 $n$ , $m$ , $k$ 가 주어진다 ( $1 \le n \le 3 \cdot 10^5$ , $0 \le m \le 3 \cdot 10^5$ , $0 \le k \le 10^{18}$ ). 각각 반복 횟수, 요구 조건의 수, 최대 복잡도이다.

다음 $m$ 개의 줄에는 두 정수 $l_i$ , $r_i$ 가 주어진다 ( $1 \le l_i < r_i \le n$ ). 모든 요구 조건은 서로 다르다.

출력

모든 요구 조건을 만족하는 효율적인 학습 계획의 개수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다.

예제2

예제 1
입력
```
2 0 3
```
예상 출력
```
9
```
예제 2
입력
```
3 1 2
1 2
```
예상 출력
```
2
```