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<cstdio>
#include<cmath>
#define For(i,A,B) for(i=(A);i<=(B);++i)
typedef long long ll;
const int P=200003;
const double pi=acos(-1.0);
const int Lim=1<<19;
int g[P],p[P],r[Lim+50];
struct cnum{
	double x,y;
	cnum(double x=0,double y=0):x(x),y(y){}
	inline cnum operator+(const cnum&b)const{return cnum(x+b.x,y+b.y);}
	inline cnum operator-(const cnum&b)const{return cnum(x-b.x,y-b.y);}
	inline cnum operator*(const cnum&b)const{return cnum(x*b.x-y*b.y,x*b.y+y*b.x);}
}a[Lim+50];
inline int Shl(int a){return (a<<=1)>=P?a-P:a;}
inline void FFT(short type){
	int i,j,M,R;
	cnum w,wn,t,tt;
	For(i,0,Lim-1)if(i<r[i]){t=a[i];a[i]=a[r[i]];a[r[i]]=t;}
	for(M=1,R=2;M<Lim;M<<=1,R<<=1){
		wn=cnum(cos(pi/M),sin(pi/M)*type);
		for(i=0;i<Lim;i+=R){
			w=cnum(1);
			For(j,0,M-1){
				t=a[i+j];tt=a[i+M+j]*w;
				a[i+j]=t+tt;a[i+M+j]=t-tt;
				w=w*wn;
			}
		}
	}
}
int main(){
	int n,i,x;
	ll ans=0ll;
	scanf("%d",&n);
	g[0]=1;
	For(i,1,P-2)p[g[i]=Shl(g[i-1])]=i;
	For(i,1,n){
		scanf("%d",&x);
		if(x){
			ans-=(ll)x*x%P;
			a[p[x]].x+=1;
		}
	}
	For(i,0,Lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<18);
	FFT(1);
	For(i,0,Lim-1)a[i]=a[i]*a[i];
	FFT(-1);
	For(i,0,P-2)ans+=(ll)((a[i].x+a[i+P-1].x)/Lim+0.5)*g[i];
	printf("%lld\n",ans>>1);
	return 0;
}