#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef complex<db> cplx;
const int N=(1<<22)+5;
const db PI=acos(-1.00);
int rev[N];
cplx omega(int n,int k,int flag){
    return cplx(cos(2*PI*k/n),flag*sin(2*PI*k/n));
}

void dft(int n,cplx *t,int typ){
    for(int i=0;i<n;i++)
        if(i<rev[i])swap(t[i],t[rev[i]]);
    for(int step=1;step<n;step<<=1){
        cplx wn=cplx(cos(PI/step),typ*sin(PI/step));//涓诲崟浣嶆牴 
        for(int i=step<<1,j=0;j<n;j+=i){
            cplx w=cplx(1.0,0);
            for(int k=0;k<step;k++,w*=wn){
                cplx x=t[j+k],y=t[j+k+step]*w;
                t[j+k]=x+y,t[j+k+step]=x-y;
            }
        }
    }
}
void fft(int P,cplx *A,cplx *B,cplx*C){
    dft(P,A,1);
    dft(P,B,1);
    for(int i=0;i<=P;i++)C[i]=A[i]*B[i];
    dft(P,C,-1);
}

cplx A[N],B[N],C[N];
int n,m;

const int mod = 200003;
int g=0;
int ig[mod];
inline void findg(){
	while(1){
		++g;
		// cout << "chk" << g << endl;
		for(int j=0;j<mod;j++)ig[j]=-1;
		int flag=0;
		// cout << ig[1] << endl;
		for(int j=0,cur=1;j<mod-1;++j,cur=1ll*cur*g%mod){
			// cout << cur << ":" << ig[cur] << endl;
			// cout << j << ":" << cur << ":" << ig[cur] << endl;
			if(ig[cur]!=-1){flag=j+1;break;}
			ig[cur]=j;
		}
		// cout << flag << endl;
		// system("pause");
		if(!flag)break;
	}
	// cout << g << endl;
}

inline int qpow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=1ll*a*a%mod){
		if(b&1)ret=1ll*ret*a%mod;
	}
	return ret;
}

int main()
{
	ll ans=0;
	findg();
	cin >> n;
	for(int i=1;i<=n;i++){
		int t;scanf("%d",&t);
		ans-=1ll*t*t%mod;
		t=ig[t];
		if(t==-1)continue;
		// cout << t << endl;
		// cout << t << ":" << qpow(g,t) << endl;
		A[t]=A[t]+1.00;
		B[t]=B[t]+1.00;
	}
    // scanf("%d%d",&n,&m);
    // for(int i=0;i<=n;i++)scanf("%lf",&A[i].real());
    // for(int i=0;i<=m;i++)scanf("%lf",&B[i].real());
    int p=1,l=0;
    while(p<=(mod*2))p<<=1,l++;
    for(int i=0;i<p;++i)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    fft(p,A,B,C);
	for(int i=0;i<mod*2;i++){
		ll x = ll(C[i].real()/p+0.5);
		// if(x!=0)cout << x << ":" << qpow(g,i) << endl;
		ans+=x*qpow(g,i);
	}
	cout << ans/2 << endl;
    // for(int i=0;i<=m+n;i++){
    //     printf("%d ",int(C[i].real()/p+0.5));
    // }
    return 0;
}

### Prompt

Generate a cpp solution to the following problem:

Let’s take a prime P = 200\,003. You are given N integers A_1, A_2, \ldots, A_N. Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

* 2 \leq N \leq 200\,000
* 0 \leq A_i < P = 200\,003
* All values in input are integers.

Input

Input is given from Standard Input in the following format.


N
A_1 A_2 \cdots A_N


Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Examples

Input

4
2019 0 2020 200002


Output

474287


Input

5
1 1 2 2 100000


Output

600013

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef complex<db> cplx;
const int N=(1<<22)+5;
const db PI=acos(-1.00);
int rev[N];
cplx omega(int n,int k,int flag){
    return cplx(cos(2*PI*k/n),flag*sin(2*PI*k/n));
}

void dft(int n,cplx *t,int typ){
    for(int i=0;i<n;i++)
        if(i<rev[i])swap(t[i],t[rev[i]]);
    for(int step=1;step<n;step<<=1){
        cplx wn=cplx(cos(PI/step),typ*sin(PI/step));//涓诲崟浣嶆牴 
        for(int i=step<<1,j=0;j<n;j+=i){
            cplx w=cplx(1.0,0);
            for(int k=0;k<step;k++,w*=wn){
                cplx x=t[j+k],y=t[j+k+step]*w;
                t[j+k]=x+y,t[j+k+step]=x-y;
            }
        }
    }
}
void fft(int P,cplx *A,cplx *B,cplx*C){
    dft(P,A,1);
    dft(P,B,1);
    for(int i=0;i<=P;i++)C[i]=A[i]*B[i];
    dft(P,C,-1);
}

cplx A[N],B[N],C[N];
int n,m;

const int mod = 200003;
int g=0;
int ig[mod];
inline void findg(){
	while(1){
		++g;
		// cout << "chk" << g << endl;
		for(int j=0;j<mod;j++)ig[j]=-1;
		int flag=0;
		// cout << ig[1] << endl;
		for(int j=0,cur=1;j<mod-1;++j,cur=1ll*cur*g%mod){
			// cout << cur << ":" << ig[cur] << endl;
			// cout << j << ":" << cur << ":" << ig[cur] << endl;
			if(ig[cur]!=-1){flag=j+1;break;}
			ig[cur]=j;
		}
		// cout << flag << endl;
		// system("pause");
		if(!flag)break;
	}
	// cout << g << endl;
}

inline int qpow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=1ll*a*a%mod){
		if(b&1)ret=1ll*ret*a%mod;
	}
	return ret;
}

int main()
{
	ll ans=0;
	findg();
	cin >> n;
	for(int i=1;i<=n;i++){
		int t;scanf("%d",&t);
		ans-=1ll*t*t%mod;
		t=ig[t];
		if(t==-1)continue;
		// cout << t << endl;
		// cout << t << ":" << qpow(g,t) << endl;
		A[t]=A[t]+1.00;
		B[t]=B[t]+1.00;
	}
    // scanf("%d%d",&n,&m);
    // for(int i=0;i<=n;i++)scanf("%lf",&A[i].real());
    // for(int i=0;i<=m;i++)scanf("%lf",&B[i].real());
    int p=1,l=0;
    while(p<=(mod*2))p<<=1,l++;
    for(int i=0;i<p;++i)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    fft(p,A,B,C);
	for(int i=0;i<mod*2;i++){
		ll x = ll(C[i].real()/p+0.5);
		// if(x!=0)cout << x << ":" << qpow(g,i) << endl;
		ans+=x*qpow(g,i);
	}
	cout << ans/2 << endl;
    // for(int i=0;i<=m+n;i++){
    //     printf("%d ",int(C[i].real()/p+0.5));
    // }
    return 0;
}

```