XOR Hashing

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

요약

0 이상 2^N 미만의 정수 x, y로 이루어진 모든 점 (x, y)에 x XOR y 값이 부여되어 있을 때, M번 중복을 허용해 균등하게 점을 뽑아 같은 해시 값이 나올 확률을 구한다.

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

문제

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

값이 부여된 좌표 중 하나를 중복을 허용하여 균등한 확률로 $M$ 번 선택할 때, 같은 해시 값이 존재할 확률을 구하여라.

입력

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

출력

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

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

예제1

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