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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005,mod=200003;
const double pi=3.141592653589793;
int n,m=524288,a[N],b[N],p[N*2],pos[N];
long long ans;
int rev[N*3];
struct complex{
	long double x,y;
	complex(){}
	complex(long double x,long double y):x(x),y(y){}
	friend complex operator + (const complex &a,const complex &b){
		return complex(a.x+b.x,a.y+b.y);
	}
	friend complex operator - (const complex &a,const complex &b){
		return complex(a.x-b.x,a.y-b.y);
	}
	friend complex operator * (const complex &a,const complex &b){
		return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
	}
}x[N*3];
void fft(complex *a,int md){
	for(int i=0;i<m;i++){
		if(i<rev[i]){
			swap(a[i],a[rev[i]]);
		}
	}
	for(int i=1;i<m;i<<=1){
		complex wn=complex(cos(pi/i),md*sin(pi/i));
		for(int j=0;j<m;j+=(i<<1)){
			complex w=complex(1,0);
			for(int k=j;k<j+i;k++,w=w*wn){
				complex x=a[k];
				complex y=w*a[k+i];
				a[k]=x+y;
				a[k+i]=x-y;
			}
		}
	}
	if(md==-1){
		for(int i=0;i<m;i++){
			a[i].x/=m;
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]%=mod;
	}
	p[0]=1;
	for(int i=1;i<=mod*2;i++){
		p[i]=p[i-1]*2%mod;
	}
	for(int i=0;i<mod;i++){
		pos[p[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(!a[i]){
			continue;
		}
		b[i]=pos[a[i]];
		x[b[i]].x++;
	}
	for(int i=0;i<m;i++){
		rev[i]=(rev[i>>1]>>1)|(i&1)*(m>>1);
	}
	fft(x,1);
	for(int i=0;i<m;i++){
		x[i]=x[i]*x[i];
	}
	fft(x,-1);
	for(int i=0;i<mod*2;i++){
		ans+=p[i]*((long long)(x[i].x+0.5));
	}
	for(int i=1;i<=n;i++){
		if(!a[i]){
			continue;
		}
		ans-=p[2*b[i]];
	}
	ans/=2;
	printf("%lld\n",ans);
	return 0;
}