#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 200003
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif

const double pi = acos(-1.0);
const int INF = 0x7fffffff;
const int N=6e5+5;
ll M,l,n,m,r[N];
ll k,b,ans,ans2;
ll a[N],v[N],g[N];
inline ll read(){
    ll x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}
struct Cp{
	double x,y;
	Cp(double _x=0,double _y=0) {x=_x,y=_y;}
	Cp operator + (const Cp& rhs) {return Cp(x+rhs.x,y+rhs.y);}
	Cp operator - (const Cp& rhs) {return Cp(x-rhs.x,y-rhs.y);}	
	Cp operator * (const Cp& rhs) {return Cp(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);}	
}A[N],B[N],x,w,w0;
inline void FFT(Cp *A,int f){
	int i,j,k;
	for(i=0;i<M;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	for(i=1;i<M;i<<=1){
		w.x=cos(pi/i),w.y=sin(pi/i)*f;
		for(j=0;j<M;j+=i<<1){
			w0.x=1,w0.y=0;
			for(k=0;k<i;k++){
				x=A[j+k];
				A[j+k]=x+(w0*A[i+j+k]),A[i+j+k]=x-(w0*A[i+j+k]);
				w0=w0*w; 
			}
		}
	}
	if(f==-1) for(i=0;i<M;i++) A[i].x/=M;
}
int main(){
#ifdef Devil_Gary
	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
#endif
	cin>>n;
	for(ll i=0,tt=1;i<mod;i++) {
		g[i]=tt,v[tt]=i;
		(tt*=2)%=mod;
	}	
//	for(int i=1;i<mod;i++) if(!v[i]) cout<<i<<endl;
	for(M=1;M<=mod+mod;M<<=1,l++);
    for(ll i=0;i<N;i++) A[i].x=a[i],A[i].y=0; 
	for(ll i=1,tmp;i<=n;i++) {
		tmp=read();
		if(!tmp) continue;
		ans2+=tmp*tmp%mod;
		A[v[tmp]].x+=1; 
	}
	for(ll i=0;i<M;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(A,1);
	for(ll i=0;i<M;i++) A[i]=A[i]*A[i];
	FFT(A,-1);
	for(ll i=0;i<mod+mod;i++){
//		if(A[i].x) bug(i),bug(A[i].x);
		ll t=(ll)(A[i].x+0.5);
//		if(t) cout<<i<<" "<<t<<endl;
		ans+=(g[i%(mod-1)]*t);
	}
	ans-=ans2,ans/=2;
//	cout<<g[235484%(mod-1)]<<" "<<g[198602%(mod-1)]<<" "<<g[236884%(mod-1)]<<endl; 
	printf("%lld\n",ans);
}
### Prompt

Please create a solution in cpp 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;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 200003
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif

const double pi = acos(-1.0);
const int INF = 0x7fffffff;
const int N=6e5+5;
ll M,l,n,m,r[N];
ll k,b,ans,ans2;
ll a[N],v[N],g[N];
inline ll read(){
    ll x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}
struct Cp{
	double x,y;
	Cp(double _x=0,double _y=0) {x=_x,y=_y;}
	Cp operator + (const Cp& rhs) {return Cp(x+rhs.x,y+rhs.y);}
	Cp operator - (const Cp& rhs) {return Cp(x-rhs.x,y-rhs.y);}	
	Cp operator * (const Cp& rhs) {return Cp(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);}	
}A[N],B[N],x,w,w0;
inline void FFT(Cp *A,int f){
	int i,j,k;
	for(i=0;i<M;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	for(i=1;i<M;i<<=1){
		w.x=cos(pi/i),w.y=sin(pi/i)*f;
		for(j=0;j<M;j+=i<<1){
			w0.x=1,w0.y=0;
			for(k=0;k<i;k++){
				x=A[j+k];
				A[j+k]=x+(w0*A[i+j+k]),A[i+j+k]=x-(w0*A[i+j+k]);
				w0=w0*w; 
			}
		}
	}
	if(f==-1) for(i=0;i<M;i++) A[i].x/=M;
}
int main(){
#ifdef Devil_Gary
	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
#endif
	cin>>n;
	for(ll i=0,tt=1;i<mod;i++) {
		g[i]=tt,v[tt]=i;
		(tt*=2)%=mod;
	}	
//	for(int i=1;i<mod;i++) if(!v[i]) cout<<i<<endl;
	for(M=1;M<=mod+mod;M<<=1,l++);
    for(ll i=0;i<N;i++) A[i].x=a[i],A[i].y=0; 
	for(ll i=1,tmp;i<=n;i++) {
		tmp=read();
		if(!tmp) continue;
		ans2+=tmp*tmp%mod;
		A[v[tmp]].x+=1; 
	}
	for(ll i=0;i<M;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(A,1);
	for(ll i=0;i<M;i++) A[i]=A[i]*A[i];
	FFT(A,-1);
	for(ll i=0;i<mod+mod;i++){
//		if(A[i].x) bug(i),bug(A[i].x);
		ll t=(ll)(A[i].x+0.5);
//		if(t) cout<<i<<" "<<t<<endl;
		ans+=(g[i%(mod-1)]*t);
	}
	ans-=ans2,ans/=2;
//	cout<<g[235484%(mod-1)]<<" "<<g[198602%(mod-1)]<<" "<<g[236884%(mod-1)]<<endl; 
	printf("%lld\n",ans);
}
```