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 ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;
const int N=1<<19|5;
const int mo=200003;
#define E complex<long double>
#define pi acos(-1)
int R[N],n,m,f[N];
E A[N];
void FFT(E *a,int p,int f){
	for (int i=0;i<p;i++)
		if (i<R[i]) swap(a[i],a[R[i]]);
	for (int d=1;d<p;d<<=1){
		E wn(cosl(pi/d),f*sinl(pi/d));
		for (int i=0;i<p;i+=(d<<1)){
			E w(1,0);
			for (int j=0;j<d;j++,w*=wn){
				E y=a[i+j+d]*w;
				a[i+j+d]=a[i+j]-y;
				a[i+j]+=y;
			}
		}
	}
	if (f==-1){
		for (int i=0;i<p;i++)
			a[i]/=p;
	}
}
ll ans;
int main(){
	int v=1;
	For(i,0,mo-2){
		f[v]=i,v=2*v%mo;
		if (i!=mo-2) assert(v!=1);
	}
	scanf("%d",&n);
	For(i,1,n){
		int x;
		scanf("%d",&x);
		if (x){
			A[f[x]]=A[f[x]]+E(1,0); 
			ans-=1ll*x*x%mo;
		}
	}
	int p=1,L=0;
	for (;p<2*mo;p<<=1,L++);
	//cout<<p<<' '<<L<<endl;
	for (int i=1;i<p;i++)
		R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	FFT(A,p,1);
	for (int i=0;i<p;i++) A[i]*=A[i];
	FFT(A,p,-1);
	v=1;
	For(i,0,2*mo){
		ans+=v*((ll)(A[i].real()+0.0001));
		v=2*v%mo;
	}
	cout<<ans/2;
}