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<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
#define N 600020
const int mod=200003;
const int G=2;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
typedef vector<int> poly;
int g[N],n,id[N],lim,cnt[N],tr[N];
ll ans;
void init(){
	int now=1;
	for(int i=0;i<mod-1;++i){
		g[i]=now;
		id[now]=i;
		now=now*G%mod;
	}
}
struct Complex{
	double x,y;
	Complex(double _x,double _y){x=_x,y=_y;} Complex(){x=y=0;}
	Complex operator +(Complex b){
		return Complex(x+b.x,y+b.y);
	}
	Complex operator -(Complex b){
		return Complex(x-b.x,y-b.y);
	}
	Complex operator *(Complex b){
		return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
	}
}f[N<<1];
void FFT(Complex *f,int flag,int n){
	for(int i=0;i<n;i++){
		if(i<tr[i])swap(f[i],f[tr[i]]);
	}
	for(int p=2;p<=n;p<<=1){
		int len=(p>>1);
		Complex wn(cos(2*PI/p),sin(2*PI/p));
		if(!flag)wn.y*=-1;
		for(int k=0;k<n;k+=p){
			Complex buf(1,0);
			for(int i=k;i<k+len;i++){
				Complex tmp=buf*f[len+i];
				f[len+i]=f[i]-tmp;
				f[i]=f[i]+tmp;
				buf=buf*wn;
			}
		}
	}
}
int main(){
	n=read();
	init();
	for(int i=1;i<=n;++i){
		int x=read();
		if(!x)continue;
		++cnt[x];
	}
	for(int i=1;i<mod;++i){
		f[id[i]].x=cnt[i];
	}
	lim=1;
	while(lim<mod<<1)lim<<=1;
	for(int i=0;i<lim;i++){
		tr[i]=((tr[i>>1]>>1)|((i&1)?lim>>1:0));
	}
	FFT(f,1,lim);
	for(int i=0;i<lim;++i){
		f[i]=f[i]*f[i];
	}
	FFT(f,0,lim);
	for(int i=0;i<mod<<1;++i){
		ans+=(ll)(f[i].x/lim+0.49)*g[i%(mod-1)];
	}
	for(int i=1;i<mod;++i){
		ans-=cnt[i]*(1LL*i*i%mod);
	}
	ans/=2;
	cout<<ans<<endl;
	return 0;
}