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 cs const
#define pb push_back
using namespace std;
cs int N = 1 << 19 | 5;
typedef long long ll;
int n, a[N], G = 2, P = 200003, b[N];
int ksm(int a, int b, int p){
	int ans = 1; for(;b;b>>=1,a=1ll*a*a%P)
	if(b&1) ans=1ll*ans*a%P; return ans;
}
int fnd(int P){
	vector<int> fc;
	for(int i = 2; i * i < P; i++)
		if((P - 1) % i == 0) fc.pb(i), fc.pb((P - 1) / i);
	for(int i = 2; ; i++){
		bool ok = 1;
		for(int z : fc) if(ksm(i, z, P) == 1) {
			ok = false; break;
		} if(ok) return i;
	}
}
cs double PI = acos(-1.0);
struct cp{
	double x, y; cp(double _x = 0, double _y = 0){ x = _x, y = _y; }
	cp operator + (cs cp &a){ return cp(x + a.x, y + a.y); }
	cp operator - (cs cp &a){ return cp(x - a.x, y - a.y); }
	cp operator * (cs cp &a){ return cp(x * a.x - y * a.y, x * a.y + y * a.x); }
} c[N];
int up, bit, rv[N];
void init(int d){
	up = 1, bit = 0; while(up < d) up <<= 1, ++bit;
	for(int i = 0; i < up; i++) 
	rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
void FFT(cp *a, int typ){
	for(int i = 0; i < up; i++) if(i < rv[i]) swap(a[i], a[rv[i]]);
	for(int i = 1; i < up; i <<= 1){
		cp wn(cos(PI / i), typ * sin(PI / i));
		for(int j = 0; j < up; j += (i << 1)){
			cp w(1, 0);
			for(int k = 0; k < i; k++, w = w * wn){
				cp x = a[k + j], y = w * a[k + j + i];
				a[k + j] = x + y, a[k + j + i] = x - y;
			}
		}
	} if(typ == -1){
		for(int i = 0; i < up; i++)
		a[i].x = a[i].x / up;
	}
}
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d", &n);
	for(int i = 0, mt = 1; i + 1 < P; i++)
		b[mt] = i, mt = 1ll * mt * G % P;
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		if(a[i]) c[b[a[i]]].x += 1;
	}
	init(P + P); 
	FFT(c, 1);
	for(int i = 0; i < up; i++) c[i] = c[i] * c[i];
	FFT(c, -1); ll ans = 0;
	for(int i = 0; i + 1 < P; i++) c[i].x += c[i + P - 1].x;
	for(int i = 0, mt = 1; i + 1 < P; i++)
		ans += (ll)(c[i].x + 0.49) * mt, mt = 1ll * mt * G % P;
	for(int i = 1; i <= n; i++) ans -= 1ll * a[i] * a[i] % P;
	cout << ans / 2; return 0;
}