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;

#define mod 200003
#define G 2
#define MAXN 8000010
#define PI 3.1415926535897932384

struct cp
{
	double real,imag;
	cp(){}
	cp(double a,double b):real(a),imag(b){}
	cp operator+(cp &c){return cp(real+c.real,imag+c.imag);}
	cp operator-(cp &c){return cp(real-c.real,imag-c.imag);}
	cp operator*(cp &c){return cp(real*c.real-imag*c.imag,real*c.imag+imag*c.real);}
	cp operator/(int x){return cp(real/x,imag/x);}
};

int n,m,l=1,tt,rev[MAXN],ln[MAXN],now=1,tmp[MAXN];
long long ans;
cp a[MAXN];

void init(int x)
{
	while(l<=x)l<<=1,++tt;
	for(int i=0;i<l;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(tt-1));
}

void fft(cp *a,int dft)
{
	for(int i=0;i<l;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int mid=1;mid<l;mid<<=1)
	{
		cp w(cos(PI/mid),dft*sin(PI/mid));
		for(int r=mid<<1,i=0;i<l;i+=r)
		{
			cp nw(1,0);
			for(int j=0;j<mid;++j)
			{
				cp x=a[i+j],y=nw*a[i+mid+j];
				a[i+j]=x+y;
				a[i+mid+j]=x-y;
				nw=nw*w;
			}
		}
	}
	if(dft==-1)for(int i=0;i<l;++i)a[i]=a[i]/l;
}

void calc()
{
	int now=1;
	for(int i=1;i<mod;++i)
	{
		now=(long long)now*G%mod;
		ln[now]=i;
	}
}

int main()
{
	calc();
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		int x;
		scanf("%d",&x);
		if(x==0)continue;
		a[ln[x]].real+=1;
		++tmp[2*ln[x]];
	}
	init(2*mod);
	fft(a,1);
	for(int i=0;i<l;++i)a[i]=a[i]*a[i];
	fft(a,-1);
	for(int i=0;i<l;++i)
	{
		ans+=now*((long long)(a[i].real-tmp[i]+.5))/2;
		now=(long long)now*G%mod;
	}
	printf("%lld\n",ans);
}