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;
int const p=200003,g=5;
double const pi=acos(-1);
int lg[200005],r[800005];
struct comp
{
	double r,i;
	comp(double a=0,double b=0){r=a,i=b;}
	friend comp operator +(comp x,comp y){return comp(x.r+y.r,x.i+y.i);}
	friend comp operator -(comp x,comp y){return comp(x.r-y.r,x.i-y.i);}
	friend comp operator *(comp x,comp y){return comp(x.r*y.r-x.i*y.i,x.i*y.r+x.r*y.i);}
}A[800005];
void fft(comp *f,int n,int op)
{
	for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);
	for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
	for(int len=2;len<=n;len<<=1)
	{
		int q=len>>1;
		comp wn=comp(cos(pi/q),op*sin(pi/q));
		for(int i=0;i<n;i+=len)
		{
			comp w=comp(1,0);
			for(int j=i;j<i+q;j++,w=w*wn)
			{
				comp d=f[j+q]*w;
				f[j+q]=f[j]-d;
				f[j]=f[j]+d;
			}
		}	
	}
	if(op==-1)
		for(int i=0;i<n;i++)
			f[i]=f[i]*comp(1.0/n,0);
}
int pw(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)res=1ll*res*x%p;
		x=1ll*x*x%p;
		y>>=1;
	}
	return res;
}
int main()
{
	long long ans=0;
	int n,now=1,x;
	scanf("%d",&n);
	lg[1]=0;
	for(int i=1;i<p-1;i++)now=now*g%p,lg[now]=i;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(!x)continue;
		cerr<<lg[x]<<endl;
		A[lg[x]].r=A[lg[x]].r+1;
		ans-=1ll*x*x%p;
	}
	int lim=1;
	while(lim<(p<<1))lim<<=1;
	fft(A,lim,1);
	for(int i=0;i<lim;i++)A[i]=A[i]*A[i];
	fft(A,lim,-1);
	for(int i=0;i<lim;i++)
		ans+=1ll*((long long)(A[i].r+0.5))*pw(g,i);
	printf("%lld",ans/2);
    return 0;
}