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;


const int mod = 200003, g = 2;

const double PI = acos(-1);
struct base {
	double a, b;
	base(double a = 0, double b = 0) : a(a), b(b) {}
	const base operator + (const base &c) const
		{ return base(a + c.a, b + c.b); }
	const base operator - (const base &c) const
		{ return base(a - c.a, b - c.b); }
	const base operator * (const base &c) const
		{ return base(a * c.a - b * c.b, a * c.b + b * c.a); }
};
void fft(vector<base> &p, bool inv = 0) {
	int n = p.size(), i = 0;
	for(int j = 1; j < n - 1; ++j) {
		for(int k = n >> 1; k > (i ^= k); k >>= 1);
		if(j < i) swap(p[i], p[j]);
	}
	for(int l = 1, m; (m = l << 1) <= n; l <<= 1) {
		double ang = 2 * PI / m;
		base wn = base(cos(ang), (inv ? 1. : -1.) * sin(ang)), w;
		for(int i = 0, j, k; i < n; i += m) {
			for(w = base(1, 0), j = i, k = i + l; j < k; ++j, w = w * wn) {
				base t = w * p[j + l];
				p[j + l] = p[j] - t;
				p[j] = p[j] + t;
			}
		}
	}
	if(inv) for(int i = 0; i < n; ++i) p[i].a /= n, p[i].b /= n;
}
vector<long long> multiply(vector<int> &a, vector<int> &b) {
	int n = a.size(), m = b.size(), t = n + m - 1, sz = 1;
	while(sz < t) sz <<= 1;
	vector<base> x(sz), y(sz), z(sz);
	for(int i = 0 ; i < sz; ++i) {
		x[i] = i < (int)a.size() ? base(a[i], 0) : base(0, 0);
		y[i] = i < (int)b.size() ? base(b[i], 0) : base(0, 0);
	}
	fft(x), fft(y);
	for(int i = 0; i < sz; ++i) z[i] = x[i] * y[i];
	fft(z, 1);
	vector<long long> ret(sz);
	for(int i = 0; i < sz; ++i) ret[i] = (long long) (z[i].a + 0.5);
	while((int)ret.size() > 1 && ret.back() == 0) ret.pop_back();
	return ret;
}

int pw[2 * mod], inv[mod];
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	pw[0] = 1;
	for (int i = 1; i < 2 * mod; i++) {
		pw[i] = pw[i - 1] * g % mod;
		if (inv[pw[i]] == 0) inv[pw[i]] = i;
	}
	int n; cin >> n;
	vector<int> a(mod);
	for (int i = 0; i < n; i++) {
		int k; cin >> k;
		if (k == 0) continue;
		a[inv[k]]++;
	}
	auto b = multiply(a, a);
	b.resize(2 * mod);
	long long ans = 0;
	for (int i = 0; i < mod; i++) b[2 * i] -= a[i];
	for (int i = 0; i < 2 * mod; i++) {
		b[i] /= 2;
		ans += 1LL * pw[i] * b[i];
	}
	cout << ans << '\n';
    return 0;
}