Molly has a math addiction. For her birthday, she receives a sequence of length ~N~ defined by ~A_i = (A_{i-1} \times B) \bmod M~. 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~.