Molly has a math addiction. For her birthday, she receives a sequence of length $N$ defined by $A_i=(A_{i-1}\times B)modM$. Given the value of $A_0$, help Molly find the sum of all pairwise products, mod ${10}^9+7$.

Input Specification

The first and only line of input will contain $N$, $A_0$, $B$, and $M$, each space-separated.

Output Specification

The output should contain a single integer, the sum of all pairwise products, mod ${10}^9+7$.

Constraints

For all subtasks:

$1\le A_0,B,M\le {10}^9$

Subtask 1 [40%]

$1\le N\le {10}^3$

Subtask 2 [40%]

$1\le N\le {10}^5$

Subtask 3 [20%]

$1\le N\le {10}^7$

Sample Input

3 6 3 100

Sample Output

2808

Explanation for Sample Output

The three numbers are $6$, $18$, and $54$. Their pairwise products are $6\times 18=108$, $6\times 54=324$, $18\times 6=108$, $18\times 54=972$, $54\times 6=324$ and $54\times 18=972$ and their sum is $2808$.