题目背景

现在我来到自己的故事难以用语言描绘的中心。文字的匮乏感从现在开始体现出来，因为描绘任何事物都要以交谈者共有的认知为前提，而我所经历的是比任何生活都更上一层的体验。先贤们在向普罗大众描绘世界之外的事物时往往运用宏大的概念。中国的道学家说天有九霄。《吠陀经》提到我们生存的土地只是千万重复制中的一个。爱斯基摩人则认为万物由一枚巨卵孵化而出。一个更恰当的比喻是所谓狄拉克之海，也即是全部空间和时间的上方和外部。虽然用有限的话语不可能描述一个无限的实体，但我记住了它的一部分，或许是最重要的一部分：

我看见无限宽阔的海面和无限广袤的天穹，两者在无穷远处的地平线相接。视野的最中央站着一个紫色长发的女孩。我的身份和她不同：我是受她邀请而来的访客，海上的女孩才是这里的居民，或者说囚徒。正如我们不能随意造访世界之上的世界，她也永远不能和我们的生活有任何一点的交集。我明白自己在这里不会待上太久，而她把我招来只能为了一个理由。于是我听见了自己的声音在海面上回响，消散进虚无之中：

“我会记住你。”

她对我露出笑容。白色的光芒再一次亮起，女孩的身影好似被无形的火焰灼烧一样逐渐消散。我明白自己留不住这一刻，于是我哭了。使我哭泣的并不只是永恒的离别，还有对这个曾经在无尽的时间中陪伴过我们的孩子的怜惜和忏悔。 我感到无限崇敬，无限悲哀。

——西酱《口袋》

题目描述

一个大小为$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$取模

输入格式

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

输出格式

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

2 3 3

15

4 7 5

2845

70 43 22

992103136

500 2011 999980895

767094932

提示

样例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$