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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const double Pi=acos(-1.0);
const int mod=200003,G=2,N=4000010;
struct CP{
	CP (double xx=0,double yy=0){x=xx,y=yy;}
	double x,y;
	CP operator + (CP const &B) const
	{return CP(x+B.x,y+B.y);}
	CP operator - (CP const &B) const
	{return CP(x-B.x,y-B.y);}
	CP operator * (CP const &B) const
	{return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
};
int tr[N];
void fft(CP *f,int n,int flag){
	for(int i=0;i<n;++i)
		if(i<tr[i]) swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		CP tg(cos(2*Pi/p),sin(2*Pi/p));
		if(flag==-1) tg.y*=-1;
		for(int k=0;k<n;k+=p){
			CP buf(1,0),tt;
			for(int l=k;l<k+len;++l)
				tt=buf*f[l+len],
				f[l+len]=f[l]-tt,
				f[l]=f[l]+tt,
				buf=buf*tg;
		}
	}
	if(flag==-1){
		for(int i=0;i<n;++i)
			f[i].x/=n;
	}
} 
CP f[N];
int Lg[N],a[N],g[N];
int ksm(int b,int n){
	int res=1;
	while(n){
		if(n&1) res=res*b%mod;
		b=b*b%mod; n>>=1;
	}
	return res;
}
void init(){
	int x=1;
	for(int i=0;i<mod-1;++i)
		g[i]=x,Lg[x]=i,x=x*G%mod;
	//for(int i=0;i<mod-1;++i)
	//	cout<<g[i]<<" ";cout<<endl;
	//cout<<"egerdf\n";
}
signed main(){
//	freopen("2.out","w",stdout);
	init();
	int n,x;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(a[i])f[Lg[a[i]]].x++;
	}
	int limit=1;
	while(limit<=((mod-1)<<1)) limit<<=1;
	//cout<<limit<<endl;
	for(int i=0;i<limit;++i)
		tr[i]=(tr[i>>1]>>1)|(i&1?limit>>1:0);
	//cout<<"segrtryhaw\n";
	fft(f,limit,1);
	for(int i=0;i<limit;++i)
		f[i]=f[i]*f[i];
	fft(f,limit,-1);
	//for(int i=0;i<limit;++i)cout<<f[i].x<<" ";cout<<endl;
	//cout<<"wegrtjrtsfh\n";
	for(int i=1;i<=n;++i)
		if(a[i])f[Lg[a[i]]+Lg[a[i]]].x--;
	int ans=0;
	//cout<<"fgrerttdfbdfgb\n";
	for(int i=0;i<limit;++i)
		ans+=(long long)(f[i].x/2+1e-1)*g[i%(mod-1)];
	cout<<ans;
	return 0;
}