Problem Description

Given a sequence of size $n$, $\{a_i\}$, where each number is within the range $[1, R]$.

For each sequence, a $n \times n$ grid can be generated, where the number in cell $(i, j)$ is $a_i \times a_j \mod P$.

For example, if the sequence is $\{1, 2, 3\}$ and $P = 5$, the generated grid is:

1 2 3
2 4 1
3 1 4

(since $2 \times 3 \mod 5 = 1$ and $3 \times 3 \mod 5 = 4$)

For a grid, the "fafacalue" is defined as the number of distinct numbers in it. For example, the above grid has 4 distinct numbers, $\{1, 2, 3, 4\}$.

Now, you need to find the sum of the "fafacalue" for all possible sequences, modulo $10^9 + 7$.

Input Format

The first line contains three positive integers $n, P, R$.

Output Format

Output the answer modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2 3 3

Sample Output #1

15

Sample Input #2

4 7 5

Sample Output #2

2845

Sample Input #3

70 43 22

Sample Output #3

992103136

Sample Input #4

500 2011 999980895

Sample Output #4

767094932

Notes

Explanation for Sample 1:

{ai} = {1, 1}:
1 1
1 1
(ans = 1)
{ai} = {1, 2}:
1 2
2 1
(ans = 2)
{ai} = {1, 3}:
1 0
0 0
(ans = 2)
{ai} = {2, 1}:
1 2
2 1
(ans = 2)
{ai} = {2, 2}:
1 1
1 1
(ans = 1)
{ai} = {2, 3}:
1 0
0 0
(ans = 2)
{ai} = {3, 1}:
0 0
0 1
(ans = 2)
{ai} = {3, 2}:
0 0
0 1
(ans = 2)
{ai} = {3, 3}:
0 0
0 0
(ans = 1)
Total is 15

It is guaranteed that $P$ is a prime number greater than or equal to 3.

For all data, $n \leq 500, P \leq 5000, R \leq 10^9$.

见题面 Input 部分

见题面 Output 部分