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:
#pragma GCC optimize("Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const double pi=acos(-1);
const int mod=200003,G=2,N=mod*3;
int lim,rev[N],gid[mod],gpw[mod],cnt[mod],n,l;
long long ans;

struct cpx{
	double x,y;
	cpx (double xx=0,double yy=0){x=xx,y=yy;}
	cpx operator + (const cpx &nt) const {return cpx(x+nt.x,y+nt.y);}
	cpx operator - (const cpx &nt) const {return cpx(x-nt.x,y-nt.y);}
	cpx operator * (const cpx &nt) const {return cpx(x*nt.x-y*nt.y,x*nt.y+y*nt.x);}
}f[N];

void fft(cpx *a,int n,int op){
	for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1){
		cpx w0(cos(pi/mid),op*sin(pi/mid));
		for(int len=mid<<1,i=0;i<lim;i+=len){
			cpx w(1,0);
			for(int j=0;j<mid;j++,w=w*w0){
				cpx x=a[i+j],y=w*a[i+mid+j];
				a[i+j]=x+y;
				a[i+mid+j]=x-y;
			}
		}
	}
}

signed main(){
	for(int i=0,mul=1;i<mod;i++,mul=mul*G%mod) gid[mul]=i,gpw[i]=mul;
	read(n);
	for(int i=1,x;i<=n;i++) if(read(x)) f[gid[x]].x++,cnt[x]++;
	for(lim=1,l=0;lim<=mod<<1;lim<<=1,l++) ;
	for(int i=0;i<lim;i++) rev[i]=rev[i>>1]>>1|(i&1)<<l-1;
	fft(f,lim,1);
	for(int i=0;i<lim;i++) f[i]=f[i]*f[i];
	fft(f,lim,-1);
	for(int i=0;i<mod<<1;i++) ans+=(long long)(f[i].x/lim+0.5)*gpw[i%(mod-1)];
	for(int i=0;i<mod;i++) ans-=cnt[i]*(1ll*i*i%mod);
	write(ans/2);
}