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>
#define mod 998244353
#define G 3
#define Gi 332748118
#define P 200003
#define PG 2
using namespace std;
typedef long long int ll;
const int maxn=1E6+5;
int n;
ll c[maxn];
inline ll qpow(ll x,ll y,ll m)
{
	ll ans=1,base=x;
	while(y)
	{
		if(y&1)
			ans=ans*base%m;
		base=base*base%m;
		y>>=1;
	}
	return ans;
}
int what[P+5];
inline void init()
{
	int now=1;
	for(int i=0;i<=P-2;++i)
	{
		what[now]=i;
		now=now*PG%P;
	}
}
typedef long double ld;
const ld pi=acos(-1);
struct com
{
	ld a,b;
	com(ld x=0,ld y=0):a(x),b(y){}
	com operator+(const com&A){return com(a+A.a,b+A.b);}
	com operator-(const com&A){return com(a-A.a,b-A.b);}
	com operator*(const com&A){return com(a*A.a-b*A.b,b*A.a+a*A.b);}
}a[maxn],b[maxn];
int r[maxn];
inline void DFT(com*A,int limit,int type)
{
	for(int i=0;i<limit;++i)
	{
		r[i]=(r[i>>1]>>1)|(i&1?limit>>1:0);
		if(i<r[i])
			swap(A[i],A[r[i]]);
	}
	for(int len=2;len<=limit;len<<=1)
	{
		com d;
		if(type==1)
			d=com(cos(2*pi/len),sin(2*pi/len));
		else
			d=com(cos(2*pi/len),-sin(2*pi/len));
		for(int i=0;i<limit/len;++i)
		{
			com w(1,0);
			for(int j=0,pos1=i*len,pos2=i*len+len/2;j<len/2;++j,++pos1,++pos2)
			{
				com a=A[pos1],b=A[pos2]*w;
				A[pos1]=a+b;
				A[pos2]=a-b;
				w=w*d;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	init();
	cin>>n;
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		ll x;
		cin>>x;
		if(x==0)
			continue;
		ans-=x*x%P;
		a[what[x]].a+=1;
	}
	for(int i=0;i<=P;++i)
		a[i].b=a[i].a;
	int limit=1;
	while(limit<=2*P)
		limit<<=1;
	DFT(a,limit,1);
	for(int i=0;i<limit;++i)
		a[i]=a[i]*a[i];
	DFT(a,limit,0);
	for(int i=0;i<=2*P;++i)
		c[i]=(ll)(a[i].b/limit/2+0.5);
	for(int i=P-1;i<=2*P;++i)
		c[i-(P-1)]+=c[i];
	for(int i=0;i<=P-2;++i)
		ans+=qpow(PG,i,P)*c[i];
	cout<<ans/2<<endl;
	return 0;
}