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:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

const ll MOD = 200003;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int conv[MOD];

const ld PI = acos(-1.0);
struct cmplx {
	ld x, y;
	ld real() {
		return x;
	}
	cmplx operator+(const cmplx &b) {
		return {x + b.x, y + b.y};
	}
	cmplx operator-(const cmplx &b) {
		return {x - b.x, y - b.y};
	}
	cmplx operator*(const cmplx &b) {
		return {x * b.x - y * b.y, x * b.y + y * b.x};
	}
	cmplx operator/(ld k) {
		return {x / k, y / k};
	}
};

void fft(cmplx *a, int k, int inv) {
	int n = (1 << k);
	for (int i = 1, j = 0; i < n; ++i) {
		int k = n;
		do j ^= (k >>= 1); while (~j & k);
		if (i < j)
			swap(a[i], a[j]);
	}
	for (int bl = 1; bl < n; bl *= 2) {
		ld ang = PI / bl;
		cmplx wadd{cos(ang), sin(ang)};
		for (int i = 0; i < n; i += 2 * bl) {
			cmplx w{1, 0};
			for (int j = i; j < i + bl; ++j, w = w * wadd) {
				cmplx u = a[j], v = a[j + bl] * w;
				a[j] = u + v, a[j + bl] = u - v;
			}
		}
	}
	if (inv) {
		reverse(a + 1, a + n);
		for (int i = 0; i < n; ++i) {
			a[i] = a[i] / n;
		}
	}
}

cmplx a[1 << 19];
ll b[1 << 19];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	ll cur = 1;
	for (int i = 0; i < MOD - 1; ++i) {
		conv[cur] = i;
		cur = (cur * 2) % MOD;
	}

	ll ans = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		ll x;
		cin >> x;
		if (x != 0) {
			ans -= (x * x) % MOD;
			a[conv[x]].x += 1;
		}
	}

	fft(a, 19, 0);
	for (int i = 0; i < (1 << 19); ++i) {
		a[i] = a[i] * a[i];
	}
	fft(a, 19, 1);

	for (int i = 0; i < (1 << 19); ++i) {
		ll x = llround(a[i].x);
		b[i % (MOD - 1)] += x;
	}

	cur = 1;
	for (int i = 0; i < MOD - 1; ++i) {
		ans += cur * b[i];
		cur = (cur * 2) % MOD;
	}
	cout << ans / 2 << "\n";

	return 0;
}