#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const int maxn=1000100;
int rev[maxn<<2],n,m;
struct Complex
{
	double x,y;
	Complex(){}
	Complex(double _x,double _y){x=_x;y=_y;}
	Complex operator +(const Complex &p)const{return Complex(x+p.x,y+p.y);}
	Complex operator -(const Complex &p)const{return Complex(x-p.x,y-p.y);}
	Complex operator *(const Complex &p)const{return Complex(x*p.x-y*p.y,x*p.y+y*p.x);}
}a[maxn<<2],b[maxn<<2];
inline void fft(Complex *f,int opt)
{
	for(int i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int p=2;p<=n;p<<=1)
	{
		int len=p>>1;
		Complex Tmp=Complex(cos(pi/len),sin(pi/len)*opt);
		for(int k=0;k<n;k+=p)
		{
			Complex buf=Complex(1,0);
			for(int l=k;l<k+len;l++)
			{
				Complex tt=buf*f[len+l];
				f[len+l]=f[l]-tt;
				f[l]=f[l]+tt;
				buf=buf*Tmp;
			}
		}
	}
}
const int mod=200003;
int N,cnt[mod],pv[mod];
int v[mod<<2];
int main()
{
	for(int i=pv[0]=1;i<mod-1;i++) pv[i]=pv[i-1]*2%mod;
	for(int i=0;i<mod-1;i++) cnt[pv[i]]=i;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int x;scanf("%d",&x);
		if(x) v[cnt[x]]++;
	}
	n=mod;m=mod;
	for(int i=0;i<mod;i++) a[i].x=b[i].x=v[i];
	int Tmp=1;for(;Tmp<=n+m;Tmp<<=1);m=n+m;n=Tmp;
	for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
	fft(a,1);fft(b,1);
	for(int i=0;i<n;i++) a[i]=a[i]*b[i];
	fft(a,-1);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		long long vi=round(a[i].x/n);
		if(i%2==0) vi-=v[i>>1];
		vi>>=1;
		ans+=1ll*pv[i%(mod-1)]*vi;
	}
	cout<<ans<<endl;
}
### Prompt

Please formulate 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;
const double pi=acos(-1);
const int maxn=1000100;
int rev[maxn<<2],n,m;
struct Complex
{
	double x,y;
	Complex(){}
	Complex(double _x,double _y){x=_x;y=_y;}
	Complex operator +(const Complex &p)const{return Complex(x+p.x,y+p.y);}
	Complex operator -(const Complex &p)const{return Complex(x-p.x,y-p.y);}
	Complex operator *(const Complex &p)const{return Complex(x*p.x-y*p.y,x*p.y+y*p.x);}
}a[maxn<<2],b[maxn<<2];
inline void fft(Complex *f,int opt)
{
	for(int i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int p=2;p<=n;p<<=1)
	{
		int len=p>>1;
		Complex Tmp=Complex(cos(pi/len),sin(pi/len)*opt);
		for(int k=0;k<n;k+=p)
		{
			Complex buf=Complex(1,0);
			for(int l=k;l<k+len;l++)
			{
				Complex tt=buf*f[len+l];
				f[len+l]=f[l]-tt;
				f[l]=f[l]+tt;
				buf=buf*Tmp;
			}
		}
	}
}
const int mod=200003;
int N,cnt[mod],pv[mod];
int v[mod<<2];
int main()
{
	for(int i=pv[0]=1;i<mod-1;i++) pv[i]=pv[i-1]*2%mod;
	for(int i=0;i<mod-1;i++) cnt[pv[i]]=i;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int x;scanf("%d",&x);
		if(x) v[cnt[x]]++;
	}
	n=mod;m=mod;
	for(int i=0;i<mod;i++) a[i].x=b[i].x=v[i];
	int Tmp=1;for(;Tmp<=n+m;Tmp<<=1);m=n+m;n=Tmp;
	for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
	fft(a,1);fft(b,1);
	for(int i=0;i<n;i++) a[i]=a[i]*b[i];
	fft(a,-1);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		long long vi=round(a[i].x/n);
		if(i%2==0) vi-=v[i>>1];
		vi>>=1;
		ans+=1ll*pv[i%(mod-1)]*vi;
	}
	cout<<ans<<endl;
}
```