#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005;
const double Pi=acos(-1);
const int P=200003;
int n,m,l,id[maxn],r[maxn<<2];
ll a[maxn];
struct Complex{
	double x,y;
	Complex(double u=0,double v=0){x=u,y=v;}
};
Complex operator + (Complex a,Complex b){
	return Complex(a.x+b.x,a.y+b.y);
}
Complex operator - (Complex a,Complex b){
	return Complex(a.x-b.x,a.y-b.y);
}
Complex operator * (Complex a,Complex b){
	return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
Complex b[maxn<<2],c[maxn<<2],s[50];
 
void FFT(Complex *f,int n,int op){
	for(int i=0;i<n;i++)
		if(i<r[i]) swap(f[i],f[r[i]]);
	Complex tmp,buf,x,y;
	for(int len=1;len<n;len<<=1){
		tmp=Complex(cos(Pi/len),op*sin(Pi/len));
		for(int R=len<<1,j=0;j<n;j+=R){
			buf=Complex(1,0);
			for(int k=0;k<len;k++){
				x=f[j+k],y=buf*f[j+k+len];
				f[j+k]=x+y;f[j+k+len]=x-y;
				buf=buf*tmp;
			}
		}
	}
}
int main()
{
	for(int i=0,x=1;i<P-1;i++) id[x]=i,x=x*2%P;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		if(x==0) continue;
		a[x]++,b[id[x]].x+=1;
//		cout<<id[x]<<endl;
	}
	int lim=1;
	for(;lim<(P<<1);lim<<=1,l++);
	for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(b,lim,1);
	for(int i=0;i<lim;i++) b[i]=b[i]*b[i];
	FFT(b,lim,-1);
	ll ans=0;
	for(ll i=0;i<P;i++) ans-=(i*i%P)*a[i];
//	(a[i]*(a[i]-1)-a[i]*a[i]);
	for(int i=0,val=1;i<lim;i++)
	{
		ans+=(ll)(b[i].x/lim+0.5)*val;
//		if((ll)(b[i].x/lim+0.5)) cout<<val<<' '<<(ll)(b[i].x+0.5)<<endl;
		val=val*2%P;
	}
	printf("%lld\n",ans/2);
	return 0;
}
### Prompt

Create a solution in CPP for 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;
const int maxn=1000005;
const double Pi=acos(-1);
const int P=200003;
int n,m,l,id[maxn],r[maxn<<2];
ll a[maxn];
struct Complex{
	double x,y;
	Complex(double u=0,double v=0){x=u,y=v;}
};
Complex operator + (Complex a,Complex b){
	return Complex(a.x+b.x,a.y+b.y);
}
Complex operator - (Complex a,Complex b){
	return Complex(a.x-b.x,a.y-b.y);
}
Complex operator * (Complex a,Complex b){
	return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
Complex b[maxn<<2],c[maxn<<2],s[50];
 
void FFT(Complex *f,int n,int op){
	for(int i=0;i<n;i++)
		if(i<r[i]) swap(f[i],f[r[i]]);
	Complex tmp,buf,x,y;
	for(int len=1;len<n;len<<=1){
		tmp=Complex(cos(Pi/len),op*sin(Pi/len));
		for(int R=len<<1,j=0;j<n;j+=R){
			buf=Complex(1,0);
			for(int k=0;k<len;k++){
				x=f[j+k],y=buf*f[j+k+len];
				f[j+k]=x+y;f[j+k+len]=x-y;
				buf=buf*tmp;
			}
		}
	}
}
int main()
{
	for(int i=0,x=1;i<P-1;i++) id[x]=i,x=x*2%P;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		if(x==0) continue;
		a[x]++,b[id[x]].x+=1;
//		cout<<id[x]<<endl;
	}
	int lim=1;
	for(;lim<(P<<1);lim<<=1,l++);
	for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(b,lim,1);
	for(int i=0;i<lim;i++) b[i]=b[i]*b[i];
	FFT(b,lim,-1);
	ll ans=0;
	for(ll i=0;i<P;i++) ans-=(i*i%P)*a[i];
//	(a[i]*(a[i]-1)-a[i]*a[i]);
	for(int i=0,val=1;i<lim;i++)
	{
		ans+=(ll)(b[i].x/lim+0.5)*val;
//		if((ll)(b[i].x/lim+0.5)) cout<<val<<' '<<(ll)(b[i].x+0.5)<<endl;
		val=val*2%P;
	}
	printf("%lld\n",ans/2);
	return 0;
}
```