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<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define pi 3.14159265358979323846
typedef long long ll;
#define double long double
struct complx
{
	double x,y;
	complx(double a=0,double b=0):x(a),y(b){}
};
complx operator+(const complx a,const complx b)
{
	return complx(a.x+b.x,a.y+b.y);
}
complx operator-(const complx a,const complx b)
{
	return complx(a.x-b.x,a.y-b.y);
}
complx operator*(const complx a,const complx b)
{
	return complx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
complx operator/(const complx a,const double b)
{
	return complx(a.x/b,a.y/b);
}
const int mod=200003;
int lim,len,rev[1000005];
void getlim(int dep)
{
	lim=1,len=0;
	while(lim<=dep) lim<<=1,len++;
	for(int i=1;i<lim;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
}
void fft(complx *a,int fl)
{
	for(int i=1;i<lim;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int k=1;k<lim;k<<=1)
	{
		complx wn(cos(pi/k),sin(pi/k));
	//	printf("k=%d,w=%f,%f\n",k,wn.x,wn.y);
		for(int i=0,r=k*2;i<lim;i+=r)
		{
			complx w(1,0);
			for(int j=0;j<k;j++,w=w*wn)
			{
				complx x=a[i+j],y=a[i+j+k]*w;
				a[i+j]=x+y;
				a[i+j+k]=x-y;
			}
		}
	}
	if(fl==-1)
	{
		reverse(a+1,a+lim);
		for(int i=0;i<lim;i++)
			a[i]=a[i]/(double)lim;
	}
}
int n,a[1000005],g[1000005],rg[1000005];
complx f[1000005];
ll ans,tans[1000005];
int main()
{
//	freopen("agc.in","r",stdin);
	int nw=1;
	for(int i=0;i<mod-1;i++)
	{
		g[nw]=i;
		rg[i]=nw;
		nw=2*nw%mod;
	}
//	for(int i=0;i<mod;i++)
	//	if(!g[i]) printf("i=%d,%d ",i,g[i]);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]) f[g[a[i]]].x=f[g[a[i]]].x+1;
	}
	getlim(500000);
	//printf("lim=%d\n",lim);
	fft(f,1);
	for(int i=0;i<lim;i++)
		f[i]=f[i]*f[i];
	fft(f,-1);
	for(int i=0;i<=500000;i++)
	{
		tans[i%(mod-1)]+=f[i].x+0.5;
		//if(floor(f[i].x)!=floor(f[i].x+1e-2)) printf("i=%d,f=%.10Lf\n",i,f[i].x);
	}
	for(int i=0;i<mod-1;i++)
		ans+=1ll*tans[i]*rg[i];
	for(int i=1;i<=n;i++)
		ans-=1ll*a[i]*a[i]%mod;
	ans/=2;
	printf("%lld",ans);
	return 0;
}