口袋里的纸飞机

题目背景

现在我来到自己的故事难以用语言描绘的中心。文字的匮乏感从现在开始体现出来,因为描绘任何事物都要以交谈者共有的认知为前提,而我所经历的是比任何生活都更上一层的体验。先贤们在向普罗大众描绘世界之外的事物时往往运用宏大的概念。中国的道学家说天有九霄。《吠陀经》提到我们生存的土地只是千万重复制中的一个。爱斯基摩人则认为万物由一枚巨卵孵化而出。一个更恰当的比喻是所谓狄拉克之海,也即是全部空间和时间的上方和外部。虽然用有限的话语不可能描述一个无限的实体,但我记住了它的一部分,或许是最重要的一部分: 我看见无限宽阔的海面和无限广袤的天穹,两者在无穷远处的地平线相接。视野的最中央站着一个紫色长发的女孩。我的身份和她不同:我是受她邀请而来的访客,海上的女孩才是这里的居民,或者说囚徒。正如我们不能随意造访世界之上的世界,她也永远不能和我们的生活有任何一点的交集。我明白自己在这里不会待上太久,而她把我招来只能为了一个理由。于是我听见了自己的声音在海面上回响,消散进虚无之中: “我会记住你。” 她对我露出笑容。白色的光芒再一次亮起,女孩的身影好似被无形的火焰灼烧一样逐渐消散。我明白自己留不住这一刻,于是我哭了。使我哭泣的并不只是永恒的离别,还有对这个曾经在无尽的时间中陪伴过我们的孩子的怜惜和忏悔。 我感到无限崇敬,无限悲哀。 ——西酱《口袋》

题目描述

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

输入输出样例

输入样例 #1

2 3 3

输出样例 #1

15

输入样例 #2

4 7 5

输出样例 #2

2845

输入样例 #3

70 43 22

输出样例 #3

992103136

输入样例 #4

500 2011 999980895

输出样例 #4

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|R|P| |---|---|---|---| |1,2|$N\leq 5$|$R\leq 5$|$R\times R<P\leq 20$| |3,4,5,6|$N\leq 15$|$R\leq 10$|$R\times R<P\leq 200$| |7,8|$N\leq 30$| |$R\times R<P\leq 500$| |9,10,11,12|$N\leq 100$| |$R\times R<P\leq 500$| |13,14,15,16|$N\leq 300$|$R\leq 10^9$|$P\leq 1000$| |17,18,19,20|$N\leq 500$|$R\leq 10^9$|$P\leq 5000$| 对于所有数据,$n\leq 500,P\leq 5000,R\leq 10^9$