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 meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;
//const u32 P=;
//inline u32 &inc(u32 &a, u32 b) {return (a+=b)<P?a:(a-=P);}
//inline u32 &dec(u32 &a, u32 b) {return (a-=b)&0x80000000?(a+=P):a;}
//inline u32 sum(u32 a, u32 b) {return (a+=b)<P?a:a-P;}
//inline u32 dif(u32 a, u32 b) {return (a-=b)&0x80000000?a+P:a;}
//u64 power(u64 a, int b) {
//	u64 ans=1;
//	for(; b; a=a*a%P, b/=2) if(b&1) ans=ans*a%P;
//	return ans;
//}
typedef double Real;
const Real PI=acos(-1);
struct Complex {
	Real re, im;
	Complex &operator+=(const Complex &o) {re+=o.re; im+=o.im; return *this;}
	Complex &operator/=(Real k) {re/=k; im/=k; return *this;}
};
Complex operator~(const Complex &a) {return {a.re, -a.im};}
Complex operator-(const Complex &a) {return {-a.re, -a.im};}
Complex operator+(const Complex &a, const Complex &b) {return {a.re+b.re, a.im+b.im};}
Complex operator-(const Complex &a, const Complex &b) {return {a.re-b.re, a.im-b.im};}
Complex operator*(const Complex &a, const Complex &b) {return {a.re*b.re-a.im*b.im, a.im*b.re+b.im*a.re};}
Complex operator/(const Complex &a, Real k) {return {a.re/k, a.im/k};}
int len;
Complex w[1<<19];
void init(int len) {
	for(int i=0; i<len/2; ++i) w[len/2+i]={cos(2*PI/len*i), sin(2*PI/len*i)};
	for(int i=len/2; --i; w[i]=w[i*2]);
}
void dft(Complex *x) {
	for(int i=1, j=0, k; i<len; ++i) {
		for(k=__builtin_ctz(len); j>>--k&1; ) j^=1<<k;
		j^=1<<k;
		if(i<j) std::swap(x[i], x[j]);
	}
	for(int i=1; i<len; i*=2)
		for(int j=0; j<len; j+=i+i)
			for(int k=0; k<i; ++k) {
				Complex z=w[i+k]*x[i+j+k];
				x[i+j+k]=x[j+k]-z;
				x[j+k]+=z;
			}
}

const int N=1<<19, P=2e5+3;
int a[P], up[P], lg[P];
long long f[N], g[P];
Complex c[N];
long long t, ans=0;
int main() {
	int n=rd();
	for(int i=0; i<n; ++i) a[i]=rd();
	for(int i=0; i<n; ++i) ans-=1llu*a[i]*a[i]%P;
	std::sort(a, a+n);
	up[0]=1;
	for(int i=1; i<P-1; ++i) up[i]=up[i-1]*2%P;
	for(int i=0; i<P-1; ++i) lg[up[i]]=i;
	len=1;
	while(len<2*P) len*=2;
	init(len);
	for(int i=0; i<n; ++i) if(a[i]) ++f[lg[a[i]]];
	for(int i=0; i<len; ++i) c[i]={(double)f[i], 0.0};
	dft(c);
	for(int i=0; i<len; ++i) c[i]=c[i]*c[i];
	std::reverse(c+1, c+len);
	dft(c);
	for(int i=0; i<len; ++i) f[i]=round(c[i].re/len);
	for(int i=0; i<len; ++i) ans+=up[i%(P-1)]*f[i];
	printf("%lld\n", ans/2);
	return 0;
}