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>
#define ll long long 
#define mod 200003
using namespace std;
const int N=200010;
const double pi=acos(-1);
int n,g=5,len,L,rev[N<<2],r[N],p[N];
ll ans;
struct C{
	double x,y;
	C(double _x=0,double _y=0):x(_x),y(_y){};
	C operator +(const C&A)const{return C(x+A.x,y+A.y);}
	C operator -(const C&A)const{return C(x-A.x,y-A.y);}
	C operator *(const C&A)const{return C(x*A.x-y*A.y,x*A.y+y*A.x);}
	C operator /(const int&t)const{return C(x/t,y/t);}
}a[N<<2],b[N<<2];
int pw(int x,int y){
	int tmp=1;
	for(;y;y>>=1,x=(ll)x*x%mod)
		if(y&1)tmp=(ll)tmp*x%mod;
	return tmp;
}
void ntt(C*A,int f){
	for(int i=0;i<len;++i)if(i<rev[i])swap(A[i],A[rev[i]]);
	for(int i=1;i<len;i<<=1){
		C wn=C(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<len;j+=i<<1){
			C w=C(1,0);
			for(int k=0;k<i;++k,w=w*wn){
				C x=A[j+k],y=w*A[j+k+i];
				A[j+k]=x+y,A[j+k+i]=x-y;
			}
		}
	}
	if(!~f)for(int i=0;i<len;++i)A[i]=A[i]/len;
}
int main(){
//	freopen("C.in","r",stdin);
//	freopen("C.out","w",stdout);
	scanf("%d",&n);
	for(int i=0,t=1;i<mod-1;++i,t=(ll)t*g%mod)p[r[t]=i]=t;
	for(int i=1,x;i<=n;++i){
		scanf("%d",&x);
		if(!x)continue; 
		a[r[x]].x+=1;
		ans-=(ll)x*x%mod; 
	}
	for(L=0,len=1;len<(mod-1<<1);len<<=1,L++);
	for(int i=1;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	ntt(a,1);
//	ntt(a,-1);
	for(int i=0;i<len;++i)b[i]=a[i]*a[i];
	ntt(b,-1);
	for(int i=0;i<mod-1;++i)ans+=(ll)(b[i].x+b[i+mod-1].x+0.5)*p[i];
	ans/=2;
	cout<<ans<<endl;
	return 0;
}