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<cstring>
#include<cmath>
using namespace std;
const int maxn=1000009;
const double pi=acos(-1.0);

int n,m;


struct Complex{
	double x,y;
	Complex(double xx=0,double yy=0){
		x=xx;y=yy;
	}
};
Complex operator + (Complex z1,Complex z2){
	return Complex(z1.x+z2.x,z1.y+z2.y);
}
Complex operator - (Complex z1,Complex z2){
	return Complex(z1.x-z2.x,z1.y-z2.y);
}
Complex operator * (Complex z1,Complex z2){
	return Complex(z1.x*z2.x-z1.y*z2.y,z1.x*z2.y+z2.x*z1.y);
}

int rev[maxn<<2];
Complex A[maxn<<2],B[maxn<<2];
void FFT(Complex *arr,int n,int f){
	int bitcnt=0;
	for(int len=1;len<n;len<<=1)++bitcnt;
	for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bitcnt-1));
	for(int i=1;i<n;++i)if(i<rev[i])swap(arr[i],arr[rev[i]]);
	
	for(int k=1;k<n;k<<=1){
		Complex wn=Complex(cos(pi/k),f*sin(pi/k));
		for(int i=0;i<n;i+=k*2){
			Complex w=Complex(1,0);
			for(int j=0;j<k;++j,w=w*wn){
				Complex x=arr[i+j],y=arr[i+j+k]*w;
				arr[i+j]=x+y;
				arr[i+j+k]=x-y;
			}
		}
	}
	if(f==-1){
		for(int i=0;i<n;++i)arr[i].x/=n;
	}
}

int read(){
	int r=0,k=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
	for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
	return r*k;
}

const int P=200003;
int g[maxn],f[maxn];
long long ans=0;
int main(){
	g[0]=1;
	for(int i=1;i<=P-2;++i)g[i]=g[i-1]*2%P;
	for(int i=0;i<=P-2;++i)f[g[i]]=i;
	int n;scanf("%d",&n);
	while(n--){
		int x;scanf("%d",&x);
		if(x==0)continue;
		ans-=1LL*x*x%P;
		A[f[x]].x++;
	}
	int len=1;
	while(len<=P*2)len<<=1;
	FFT(A,len,1);
	for(int i=0;i<len;++i)A[i]=A[i]*A[i];
	FFT(A,len,-1);
	long long x=1;
	for(int i=0;i<len;++i){
		long long cnt=(long long)(A[i].x+0.5);
		ans=ans+cnt*x;
		x=x*2%P;
	}
	printf("%lld\n",ans/2);
	
	return 0;
}