#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int Mod=200003,G=2,MAXN=6e5+5;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,K[MAXN],o[MAXN],a[MAXN];ll ans[MAXN];
namespace Solve{
	const double pie=acos(-1);
	struct cp{double x,y;cp(){}cp(double x,double y):x(x),y(y){}inline cp conj(){return cp(x,-y);}}w[2][MAXN],aa[MAXN],bb[MAXN],cc[MAXN],dd[MAXN];
	inline cp operator+(cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
	inline cp operator-(cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
	inline cp operator*(cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
	int r[MAXN],N,inv[MAXN],cnt;
	inline int Trans(int n){
		int N,c;
		for(N=1,c=0;N<=n;N<<=1,c++);
		for(int i=0;i<N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(c-1));
		for(int i=0;i<N;i++)w[0][i]=cp(cos(2*pie*i/N),sin(2*pie*i/N)),w[1][i]=cp(cos(2*pie*i/N),-sin(2*pie*i/N));
		return N;
	}
	inline void FFT(cp*F,int len,int opt){
		for(int i=0;i<len;i++)if(i<r[i])swap(F[i],F[r[i]]);
		for(int i=1,x=len>>1;i<len;i<<=1,x>>=1)
			for(int j=0;j<len;j+=i<<1)
				for(int k=0;k<i;k++){
					cp tt=w[opt][k*x]*F[i+j+k];
					F[i+j+k]=F[j+k]-tt,F[j+k]=F[j+k]+tt;
				}
		if(opt)for(int i=0;i<len;i++)F[i].x/=len,F[i].y/=len;
	}
	inline void MTT(int n,int*A,int*B,ll*C){
		int N=Trans(n);
		for(int i=0;i<N>>1;i++)aa[i]=cp(A[i]>>15,A[i]&0x7fff),bb[i]=cp(B[i]>>15,B[i]&0x7fff),aa[i+(N>>1)]=bb[i+(N>>1)]=cp(0,0);
		FFT(aa,N,0),FFT(bb,N,0);
		for(int i=0,j;i<N;i++){j=(N-i)&(N-1);
			cp a=(aa[i]+aa[j].conj())*cp(0.5,0),b=(aa[i]-aa[j].conj())*cp(0,-0.5),c=(bb[i]+bb[j].conj())*cp(0.5,0),d=(bb[i]-bb[j].conj())*cp(0,-0.5);
			cc[i]=a*c+a*d*cp(0,1),dd[i]=b*c+b*d*cp(0,1);
		}
		FFT(cc,N,1),FFT(dd,N,1);
		for(int i=0;i<N;i++){
			ll a=(ll)(cc[i].x+0.5),b=(ll)(cc[i].y+0.5),c=(ll)(dd[i].x+0.5),d=(ll)(dd[i].y+0.5);
			C[i]=(((ll)a<<30)+((ll)(b+c)<<15)+d);
		}
	}
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();int tmp=1;
	Rep(i,0,Mod-2)o[tmp]=i,tmp=1ll*tmp*G%Mod;
	Rep(i,1,n){
		int x=read();a[i]=x;
		if(!x)continue;
		K[o[x]]++;
	}
	Solve::MTT(Mod*2,K,K,ans);tmp=1;ll Ans=0;
	Rep(i,0,2*Mod)Ans+=1ll*ans[i]*tmp,tmp=1ll*tmp*G%Mod;
	Rep(i,1,n)Ans-=1ll*a[i]*a[i]%Mod;Ans/=2;
	cout<<Ans<<"\n"; 
//	Rep(i,0,2*Mod)cout<<ans[i]<<"\n";
	return 0;
}


### Prompt

Construct a CPP code solution to the problem outlined:

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>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int Mod=200003,G=2,MAXN=6e5+5;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,K[MAXN],o[MAXN],a[MAXN];ll ans[MAXN];
namespace Solve{
	const double pie=acos(-1);
	struct cp{double x,y;cp(){}cp(double x,double y):x(x),y(y){}inline cp conj(){return cp(x,-y);}}w[2][MAXN],aa[MAXN],bb[MAXN],cc[MAXN],dd[MAXN];
	inline cp operator+(cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
	inline cp operator-(cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
	inline cp operator*(cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
	int r[MAXN],N,inv[MAXN],cnt;
	inline int Trans(int n){
		int N,c;
		for(N=1,c=0;N<=n;N<<=1,c++);
		for(int i=0;i<N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(c-1));
		for(int i=0;i<N;i++)w[0][i]=cp(cos(2*pie*i/N),sin(2*pie*i/N)),w[1][i]=cp(cos(2*pie*i/N),-sin(2*pie*i/N));
		return N;
	}
	inline void FFT(cp*F,int len,int opt){
		for(int i=0;i<len;i++)if(i<r[i])swap(F[i],F[r[i]]);
		for(int i=1,x=len>>1;i<len;i<<=1,x>>=1)
			for(int j=0;j<len;j+=i<<1)
				for(int k=0;k<i;k++){
					cp tt=w[opt][k*x]*F[i+j+k];
					F[i+j+k]=F[j+k]-tt,F[j+k]=F[j+k]+tt;
				}
		if(opt)for(int i=0;i<len;i++)F[i].x/=len,F[i].y/=len;
	}
	inline void MTT(int n,int*A,int*B,ll*C){
		int N=Trans(n);
		for(int i=0;i<N>>1;i++)aa[i]=cp(A[i]>>15,A[i]&0x7fff),bb[i]=cp(B[i]>>15,B[i]&0x7fff),aa[i+(N>>1)]=bb[i+(N>>1)]=cp(0,0);
		FFT(aa,N,0),FFT(bb,N,0);
		for(int i=0,j;i<N;i++){j=(N-i)&(N-1);
			cp a=(aa[i]+aa[j].conj())*cp(0.5,0),b=(aa[i]-aa[j].conj())*cp(0,-0.5),c=(bb[i]+bb[j].conj())*cp(0.5,0),d=(bb[i]-bb[j].conj())*cp(0,-0.5);
			cc[i]=a*c+a*d*cp(0,1),dd[i]=b*c+b*d*cp(0,1);
		}
		FFT(cc,N,1),FFT(dd,N,1);
		for(int i=0;i<N;i++){
			ll a=(ll)(cc[i].x+0.5),b=(ll)(cc[i].y+0.5),c=(ll)(dd[i].x+0.5),d=(ll)(dd[i].y+0.5);
			C[i]=(((ll)a<<30)+((ll)(b+c)<<15)+d);
		}
	}
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();int tmp=1;
	Rep(i,0,Mod-2)o[tmp]=i,tmp=1ll*tmp*G%Mod;
	Rep(i,1,n){
		int x=read();a[i]=x;
		if(!x)continue;
		K[o[x]]++;
	}
	Solve::MTT(Mod*2,K,K,ans);tmp=1;ll Ans=0;
	Rep(i,0,2*Mod)Ans+=1ll*ans[i]*tmp,tmp=1ll*tmp*G%Mod;
	Rep(i,1,n)Ans-=1ll*a[i]*a[i]%Mod;Ans/=2;
	cout<<Ans<<"\n"; 
//	Rep(i,0,2*Mod)cout<<ans[i]<<"\n";
	return 0;
}


```