Hash Hacking

Yeondu, the operator of Green.com, has stopped storing passwords as plain text. From now on, passwords will be stored after applying a hash function. The only hash function Yeondu knows is the rolling hash function often used in competitive programming problems, so Yeondu decided to adapt it.

A Green.com password must have exactly $N$ characters, and each character must be one of $M$ allowed characters. If you map each allowed character to an integer starting from $0$, a password can be written as an array $P = [P_0, P_1, \dots, P_{N-1}]$ of length $N$ where every element is between $0$ and $M-1$ inclusive.

After the password is written as $P$, the following hash function $h$ is applied using a predetermined integer $A$.

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

For example, take $P = [10, 30, 20]$, $A = 7$, and $M = 55$. Then $h(P) = (10 \cdot 7^0 + 30 \cdot 7^1 + 20 \cdot 7^2) \bmod 55 = (10 + 210 + 980) \bmod 55 = 45$. Here $\bmod$ is the remainder operation, and since $1200 = 21 \cdot 55 + 45$, we have $1200 \bmod 55 = 45$. The hash value is always an integer between $0$ and $M-1$ inclusive.

Jaehyun hacked the hash of an administrator account at Green.com and wants to work backward to find the original password. Green.com allows $M^N$ passwords in total. Jaehyun wants to know how many of them have the hash value he recovered. Compute this count for him.

The first line contains three integers $N$, $M$, and $A$ ($1 \le N, M, A \le 5\,000\,000$).

The second line contains the recovered hash value $H$ ($0 \le H < M$).

Print the number of passwords whose hash value is $H$, modulo $1\,000\,000\,007$ ($= 10^9 + 7$).