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>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const md = 200003;
int id[md], rv[md];
vector<int> fr(md - 1);

typedef complex<double> unr;
double const pi = acos(-1.0);
int ps = 2;
vector<unr> w { unr(0, 0), unr(1, 0) };

void fftpre(int n){
	if (ps >= n)return;
	w.resize(n);
	while (ps < n){
		double th = pi / ps;
		f(i, ps, ps << 1){
			double cth = th * (i - ps);
			w[i] = unr(cos(cth), sin(cth));
		}
		ps <<= 1;
	}
}

void fft(vector<unr> &v, bool inv = false){
	int n = v.size(), j = 0;
	fftpre(n);
	f(i, 1, n){
		int z = n >> 1;
		while (j & z)j ^= z, z >>= 1;
		j ^= z;
		if (i < j)swap(v[i], v[j]);
	}
	for (int m = 1; m < n; m <<= 1)for (int i = 0; i < n; i += m << 1)f(k, 0, m){
		unr a = v[i + k], b = (inv ? conj(w[m + k]) : w[m + k]) * v[i + k + m];
		v[i + k] = a + b;
		v[i + k + m] = a - b;
	}
	if (inv)f(i, 0, n)v[i] /= n;
}

vector<ll> ml(vector<int> const &a, vector<int> const &b){
	int m = a.size() + b.size() - 1, n = 1;
	while (n < m)n <<= 1;
	vector<unr> v1(n), v2(n);
	f(i, 0, a.size())v1[i].real(a[i]);
	f(i, 0, b.size())v1[i].imag(b[i]);
	fft(v1);
	f(i, 0, n){
		unr x = v1[i], y = conj(v1[i ? n - i : i]);
		v2[i] = (x + y) * (x - y) * unr(0, -0.25);
	}
	fft(v2, true);
	vector<ll> an(m);
	f(i, 0, m)an[i] = v2[i].real() + 0.5;
	return an;
}

int main(){
	int x = 1, c = 0;
	do{
		id[x] = c;
		rv[c] = x;
		++c;
		x = 2 * x % md;
	}while (x != 1);
	
	int n;
	scanf("%d", &n);
	f(i, 0, n){
		int t;
		scanf("%d", &t);
		if (t)++fr[id[t]];
	}
	
	vector<ll> z = ml(fr, fr);
	ll an = 0;
	f(i, 0, z.size()){
		int j = i >= md - 1 ? i - md + 1 : i;
		an += rv[j] * z[i];
	}
	f(i, 0, fr.size())an -= rv[i * 2 % (md - 1)] * (ll)fr[i];
	printf("%lld\n", an >> 1);
}