Background

Now I have come to the center of my own story, which is hard to describe with words. From this moment on, the lack of language begins to show, because describing anything depends on shared understanding between speakers, and what I experienced was an experience beyond any ordinary life. When the sages described things beyond this world to the public, they often used grand concepts. Chinese Taoist scholars say the heavens have nine layers. The Vedas mention that the land we live on is only one of countless copies. The Eskimos believe that everything hatched from a giant egg. A more suitable metaphor is the so-called Dirac sea, that is, above and outside all space and time. Although it is impossible to describe an infinite entity with limited words, I remembered a part of it, perhaps the most important part:

I saw an infinitely wide sea and an infinitely vast sky, meeting at the horizon infinitely far away. At the very center of my view stood a girl with long purple hair. My identity was different from hers: I was a visitor invited by her, while the girl on the sea was the resident here, or rather, a prisoner. Just as we cannot freely visit a world above our world, she can never have even the slightest intersection with our life. I understood that I would not stay here for long, and she could only have called me here for one reason. Then I heard my own voice echo over the sea, fading into the void:

“I will remember you.”

She smiled at me. The white light lit up once again, and the girl’s figure gradually dissipated as if scorched by invisible flames. I understood that I could not keep this moment, so I cried. What made me cry was not only the eternal farewell, but also pity and remorse for this child who had once accompanied us through endless time.
I felt infinite reverence, infinite sorrow.

— Xi Jiang, “Pocket”.

Problem 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