Description

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

For each sequence, you can generate an $n\times n$ grid, where the value in cell $(i,j)$ is $a_i\times a_j \bmod P$.

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

1 2 3
2 4 1
3 1 4(因为2*3%5=1,3*3%5=4)

For a grid, define its “fafa value” as the number of distinct values appearing in it. For the grid above, it is $4$, i.e. $\{1,2,3,4\}$.

Now you need to compute the sum of the fafa values over all sequences, and take it modulo $10^9+7$.

Input Format

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

Output Format

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

2 3 3

15

4 7 5

2845

70 43 22

992103136

500 2011 999980895

767094932

Hint

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 with $P\geq 3$.

Constraints

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

Translated by ChatGPT 5