XOR Hashing

$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$의 모듈러 곱셈 역원이다.

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