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 rep(i,x,y) for(int i=x;i<=y;i++)
const int P=200003;
int pw[P],id[P];
const int N=524288;
const double pi=acos(-1.);
struct complex{
	double x,y;
	complex(double _x=0.,double _y=0.){x=_x,y=_y;}
	complex operator+(const complex&rhs){return complex(x+rhs.x,y+rhs.y);}
	complex operator-(const complex&rhs){return complex(x-rhs.x,y-rhs.y);}
	complex operator*(const complex&rhs){return complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);}
}A[N];
using ll=int64_t;
int rev[N];
ll result[N];
void dft(complex*f,int tp){
	for(int i=0;i<N;i++)if(i<rev[i])std::swap(f[i],f[rev[i]]);
	for(int len=1;len<N;len<<=1){
		complex wn(cos(pi/len),sin(pi/len)*tp);
		for(int i=0;i<N;i+=len<<1){
			complex w(1,0);rep(j,0,len-1){complex x=f[i+j],y=f[i+j+len]*w;f[i+j]=x+y;f[i+j+len]=x-y;w=w*wn;}
		}
	}
	if(tp==-1)for(int i=0;i<N;i++)result[i]=(ll)(f[i].x/N+.5);
}
int a[N];
int main(){
	pw[0]=1;
	rep(i,0,N-1)rev[i]=rev[i>>1]>>1|(i&1)<<18;
	rep(i,1,P-1)pw[i]=pw[i-1]*2%P;
	rep(i,0,P-1)id[pw[i]]=i;
	int n;
	scanf("%d",&n);
	rep(i,1,n){
		int x;
		scanf("%d",&x);
		if(x)A[id[x]].x++;
		a[i]=x;
	}
	dft(A,1);
	rep(i,0,N-1)A[i]=A[i]*A[i];
	dft(A,-1);
	rep(i,1,n)if(a[i])result[id[a[i]]*2]--;
	ll answer=0;
	rep(i,0,N-1)answer+=result[i]/2*pw[i%(P-1)];
	printf("%lld\n",answer);
	return 0;
}