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<iostream>
#include<cmath>
#define LL long long
#define DB double
using namespace std;

const int M=2e5+3;
const DB pi=acos(-1.0);
struct XS
{
	double s,f;
}a[M<<2],b[M<<2];
XS operator +(XS x,XS y)
{
	XS t;
	t.s=x.s+y.s;
	t.f=x.f+y.f;
	return t;
}
XS operator -(XS x,XS y)
{
	XS t;
	t.s=x.s-y.s;
	t.f=x.f-y.f;
	return t;
}
XS operator *(XS x,XS y)
{
	XS t;
	t.s=x.s*y.s-x.f*y.f;
	t.f=x.s*y.f+x.f*y.s;
	return t;
}
int fftn;
int rk[M<<2];
void fft(XS *A,DB type)
{
	int i,j,k;
	for(i=0;i<fftn;i++)
		if(i<rk[i]) swap(A[i],A[rk[i]]);
	for(i=1;i<fftn;i<<=1)
	{
		XS t1; t1.s=cos(pi/i); t1.f=sin(pi/i)*type;
		for(j=0;j<fftn;j+=(i<<1))
		{
			XS t2; t2.s=1; t2.f=0;
			for(k=0;k<i;k++)
			{
				XS t3=A[k+j],t4=t2*A[k+j+i];
				A[k+j]=t3+t4;
				A[k+j+i]=t3-t4;
				t2=t2*t1;
			}
		}
	}
}
void mul(XS *A,XS *B,int l)
{
	int i,j=1;
	l<<=1;
	while((1<<j)<l) j++;
	for(i=0;i<(1<<j);i++)
		rk[i]=(rk[i>>1]>>1)|((i&1)<<(j-1));
	fftn=1<<j;
	fft(A,1); fft(B,1);
	for(i=0;i<fftn;i++)
		A[i]=A[i]*B[i];
	fft(A,-1);
}
int n;
LL ans=0;
int g[M+5],pow2[M+5];
int main()
{
	int i;
	LL j=1;
	for(i=0;i<M-1;i++)
	{
		g[j]=i;
		pow2[i]=j;
		j=j*2%M;
	}
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&j);
		if(j==0) continue;
		a[g[j]].s+=1;
		b[g[j]].s+=1;
		ans-=j*j%M;
	}
	mul(a,b,M);
	for(i=0;i<fftn;i++)
		ans+=(LL)(a[i].s/fftn+0.5)*pow2[i%(M-1)];
	printf("%lld",ans>>1);
	return 0;
}