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<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define N 800002
const int p=200003;
struct px
{
	double x,y;
	friend px operator+(px a,px b){return (px){a.x+b.x,a.y+b.y};}
	friend px operator-(px a,px b){return (px){a.x-b.x,a.y-b.y};}
	friend px operator*(px a,px b)
	{return (px){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
};
int rev[N],bin[N],lg[N],n,a[N];
ll ans;
px ta[N];
double pi=acos(-1.0);
void fft(px x[],int len,double mde)
{
	for(int i=0;i<len;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
	for(int i=2;i<=len;i<<=1)
	{
		px wn=(px){cos(2.0*pi/(double)i),sin(mde*pi/(double)i)};
		for(int j=0,stp=i>>1;j<len;j+=i)
		{px w=(px){1,0};
			for(int k=j;k<j+stp;k++)
			{
				px t1=x[k],t2=x[k+stp]*w;
				x[k]=t1+t2,x[k+stp]=t1-t2;w=w*wn;
			}
		}
	}if(mde<0)for(int i=0;i<len;i++)x[i].x/=(double)len;
}
int main()
{
	bin[0]=1;lg[1]=0;
	for(int i=1;i<p-1;i++)bin[i]=2*bin[i-1]%p,lg[bin[i]]=i;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;scanf("%d",&x);a[i]=x;
		if(x)ta[lg[x]].x+=1;
	}
	int tle=1;while(tle<(p<<1))tle<<=1;
	for(int i=1;i<=tle;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if(i&1)rev[i]|=tle>>1;
	}
	fft(ta,tle,2.0);
	for(int i=0;i<tle;i++)ta[i]=ta[i]*ta[i];
	fft(ta,tle,-2.0);
	for(int i=p-1;i<2*p;i++)ta[i-(p-1)].x+=ta[i].x;
	for(int i=0;i<p-1;i++)
	{
		ans+=((ll)(ta[i].x+0.5))*bin[i];
	}
	for(int i=1;i<=n;i++)ans-=1ll*a[i]*a[i]%p;
	printf("%lld\n",ans/2);
}
/*
4
2019 0 2020 200002
*/