XOR 해싱

면접 대비

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

요약

각 해시값이 같은 확률로 나오는 점을 M번 무작위로 고를 때, 해시값이 같은 두 점이 있을 확률을 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 4점
유형: 확률, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

$x$ 좌표와 $y$ 좌표가 각각 $0$ 이상 $2^N$ 미만인 정수인 평면 위의 모든 점에, $x$ 좌표와 $y$ 좌표를 XOR한 값을 부여한다. 이처럼 데이터를 다른 데이터로 대응시키는 것을 해싱이라고 하고, 대응된 값을 해시 값이라고 한다.

값이 부여된 좌표 중 하나를 균등한 확률로 골라 $M$ 번 선택한다. 같은 좌표를 중복하여 선택할 수 있다. 이때 선택한 좌표들 중에 같은 해시 값을 가진 것이 존재할 확률을 구하여라.

입력

첫 번째 줄에 정수 $N$ , $M$ 이 공백으로 구분되어 주어진다. $(1 \leq N \leq 20;$ $1 \leq M \leq 10^9)$

출력

같은 해시 값이 존재할 확률을 $\frac{p}{q}$ 라 하자. 여기서 $p$ 와 $q$ 는 서로소인 음이 아닌 정수이고, $q\not\equiv 0 \pmod{10^9+7}$ 이다. $p\times q^{-1}\bmod (10^9+7)$ 을 출력한다. $q^{-1}$ 은 $q$ 의 모듈러 곱셈 역원이다.

구해야 하는 확률이 항상 유리수임을 증명할 수 있다.

예제1

예제 1
입력
```
2 3
```
예상 출력
```
625000005
```