Count Pairs CodeForces - 1188B 推式子

You are given a prime number pp , nn integers a1,a2,…,ana1,a2,…,an , and an integer kk .

Find the number of pairs of indexes (i,j)(i,j) (1≤i<j≤n1≤i<j≤n ) for which (ai+aj)(a2i+a2j)≡kmodp(ai+aj)(ai2+aj2)≡kmodp .

Input

The first line contains integers n,p,kn,p,k (2≤n≤3⋅1052≤n≤3⋅105 , 2≤p≤1092≤p≤109 , 0≤k≤p−10≤k≤p−1 ). pp is guaranteed to be prime.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤p−10≤ai≤p−1 ). It is guaranteed that all elements are different.

Output

Output a single integer — answer to the problem.

Examples

Input

3 3 0
0 1 2

Output

1

Input

6 7 2
1 2 3 4 5 6

Output

3

Note

In the first example:

(0+1)(02+12)=1≡1mod3(0+1)(02+12)=1≡1mod3 .

(0+2)(02+22)=8≡2mod3(0+2)(02+22)=8≡2mod3 .

(1+2)(12+22)=15≡0mod3(1+2)(12+22)=15≡0mod3 .

So only 11 pair satisfies the condition.

In the second example, there are 33 such pairs: (1,5)(1,5) , (2,3)(2,3) , (4,6)(4,6) .

、震惊，居然是道大水题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+15;
ll a[maxn];
map<long long,long long>mp;
int main()
{
    ll n,p,k;
    cin>>n>>p>>k;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        long long tp1=(a[i]*a[i]%p*a[i]%p*a[i]%p-k*a[i]%p+p)%p;
        mp[tp1]++;
    }
    long long ans=0;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        ans+=(it->second)*((it->second)-1)/2;
    }
    cout<<ans;
}