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>

typedef long long int64;
typedef std::complex<double> C;

const int N = 4e5, MOD = 2e5 + 3, G = 2;
const double PI = acos(-1);

int n;
int64 cnt[N + 5];
std::unordered_map<int, int> map;

inline int power(int x, int k, int mod) {
	int ans = 1;
	for (; k > 0; k >>= 1, x = (int64)x * x % mod) {
		if (k & 1) {
			ans = (int64)ans * x % mod;
		}
	}
	return ans;
}
inline int inv(int x, int mod) {
	return pow(x, mod - 2);
}
void fft(C *a, int k, bool opt) {
	int n = 1 << k;
	std::vector<int> rev(n);
	for (int i = 0; i < n; i++) {
		rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
		if (i < rev[i]) {
			std::swap(a[i], a[rev[i]]);
		}
	}
	for (int l = 1; l < n; l <<= 1) {
		C w = C(cos(PI / l), sin(PI / l));
		for (int i = 0; i < n; i += l << 1) {
			C wk = C(1, 0);
			for (int j = 0; j < l; j++, wk *= w) {
				C x = a[i + j + l] * wk;
				a[i + j + l] = a[i + j] - x;
				a[i + j] += x;
			}
		}
	}
	if (opt) {
		std::reverse(a + 1, a + n);
		for (int i = 0; i < n; i++) {
			a[i] /= n;
		}
	}
}
void dft(C *a, int k) {
	fft(a, k, false);
}
void idft(C *a, int k) {
	fft(a, k, true);
}
void selfMul(int64 *a) {
	static C b[1 << 19];
	int k = 19, n = 1 << k;
	std::fill(b, b + n, C(0, 0));
	for (int i = 0; i < MOD; i++) {
		b[i] = C(a[i], 0);
	}
	dft(b, k);
	for (int i = 0; i < n; i++) {
		b[i] *= b[i];
	}
	idft(b, k);
	for (int i = 0; i < MOD * 2; i++) {
		a[i] = (int64)(b[i].real() + 0.5);
	}
}
int main() {
	scanf("%d", &n);
	for (int w = 1, i = 0; i < MOD; i++, w = (int64)w * G % MOD) {
		map[w] = i;
	}
	int64 ans = 0;
	for (int x, i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (x > 0) {
			ans -= (int64)x * x % MOD;
			cnt[map[x]]++;
		}
	}
	selfMul(cnt);
	for (int w = 1, i = 0; i < MOD * 2; i++, w = (int64)w * G % MOD) {
		ans += cnt[i] * w;
	}
	printf("%lld\n", ans / 2);
	return 0;
}