Description

一个大小为$n$的数列$\{a_i\}$，每个数都在范围$[1,R]$中

对于每种数列，可以生成一个$n\times n$的网格，其中格子$(i,j)$中的数为$a_i\times a_j \mod P$

比如，如果数列是$\{1,2,3\},P=5$，则生成的网格为

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

对于一个网格，定义法法值为其中不同的数个数，比如上面那个就是4个数，即$\{1,2,3,4\}$。

现在你需要对所有数列的法法值的和对$10^9+7$取模

Input Format

第一行输入正整数$n,P,R$

Output Format

输出答案对$10^9+7$取模

2 3 3

15

4 7 5

2845

70 43 22

992103136

500 2011 999980895

767094932

Hint

样例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)
一共为15

保证$P$为大于等于3的质数

对于所有数据，$n\leq 500,P\leq 5000,R\leq 10^9$