해시 해킹

그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하던 잘못을 고치고, 이제부터 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수는 알고리즘 문제 풀이에 많이 쓰이는 롤링 해시 함수뿐이라, 이를 응용해 쓰기로 했다.

그린닷컴의 비밀번호는 길이가 정확히 $N$이어야 하며, 비밀번호를 이루는 문자는 지정된 $M$개의 문자 중 하나여야 한다. 사용 가능한 각 문자를 0부터 차례로 정수에 대응시키면, 비밀번호는 길이가 $N$이고 모든 원소가 0 이상 $M-1$ 이하인 배열 $P = [P_0, P_1, \dots, P_{N-1}]$로 나타낼 수 있다.

비밀번호를 배열 $P$로 나타낸 뒤에는, 미리 정해진 정수 $A$를 이용해 다음 해시 함수 $h$를 적용한다.

$h(P) = (P_0 \cdot A^0 + P_1 \cdot A^1 + \dots + P_{N-1} \cdot A^{N-1}) \bmod M$

예를 들어 $P = [10, 30, 20]$, $A = 7$, $M = 55$인 경우를 보자. 이때 $h(P) = (10 \cdot 7^0 + 30 \cdot 7^1 + 20 \cdot 7^2) \bmod 55 = (10 + 210 + 980) \bmod 55 = 45$이다. 여기서 $\bmod$는 나머지 연산이며, $1200 = 21 \cdot 55 + 45$이므로 $1200 \bmod 55 = 45$이다. 해시값은 항상 0 이상 $M-1$ 이하의 정수이다.

그린닷컴 관리자 계정의 비밀번호 해시값을 알아낸 재현이는 이 값으로 원래 비밀번호를 역추적하려고 한다. 그린닷컴에서 사용 가능한 비밀번호는 모두 $M^N$개인데, 그중 알아낸 해시값과 일치하는 비밀번호가 몇 개인지 구해 달라.

첫째 줄에 비밀번호의 길이 $N$, 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$)

둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$)

해시값이 $H$인 비밀번호의 개수를 $1\,000\,000\,007$ ($= 10^9 + 7$)로 나눈 나머지를 출력한다.