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 LL;

const int MOD = 2e5 + 3, G = 2, MAXN = 2e5 + 10, MAXM = 1 << 19 | 1;
const double PI = acos(-1.);

int n;
int powG[MAXN], logG[MAXN], cnt[MAXN], rev[MAXM];
struct Complex {
	double x, y;
	Complex(double x = 0, double y = 0): x(x), y(y) {}
	inline friend Complex operator+ (const Complex &a, const Complex &b) { return Complex(a.x + b.x, a.y + b.y); }
	inline friend Complex operator- (const Complex &a, const Complex &b) { return Complex(a.x - b.x, a.y - b.y); }
	inline friend Complex operator* (const Complex &a, const Complex &b) { return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
} A[MAXM], B[MAXM];

inline void init() {
	powG[0] = 1, logG[1] = 0;
	for (int i = 1; i <= MOD - 2; ++i) powG[i] = G * powG[i - 1] % MOD, logG[powG[i]] = i;
}

inline void trans(Complex *A, int n, int opt) {
	for (int i = 0; i < n; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
	for (int i = 2; i <= n; i <<= 1) {
		int mid = i >> 1; Complex Wn(cos(PI / mid), sin(PI / mid));
		for (int j = 0; j < n; j += i) {
			Complex W(1, 0);
			for (int k = 0; k < mid; ++k, W = W * Wn) {
				Complex X = A[j | k], Y = W * A[j | k | mid];
				A[j | k] = X + Y, A[j | k | mid] = X - Y;
			}
		}
	}
	if (opt) {
		std::reverse(A + 1, A + n);
		for (int i = 0; i < n; ++i) A[i].x /= n;
	}
}
inline void DFT(Complex *A, int n) { trans(A, n, 0); }
inline void IDFT(Complex *A, int n) { trans(A, n, 1); }

int main() {
	init();
	scanf("%d", &n);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), x && (++cnt[logG[x]]);
	for (int i = 0; i <= MOD; ++i) A[i].x = B[i].x = cnt[i];
	int lim = 1, index = 0;
	for (; lim < MOD << 1; lim <<= 1, ++index);
	for (int i = 1; i < lim; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (index - 1));
	DFT(A, lim), DFT(B, lim);
	for (int i = 0; i < lim; ++i) A[i] = A[i] * B[i];
	IDFT(A, lim);
	LL ans = 0;
	for (int i = 0; i < lim; ++i) ans += llround(A[i].x) * powG[i % (MOD - 1)];
	for (int i = 0; i <= MOD; ++i) ans -= 1LL * cnt[i] * (1LL * powG[i] * powG[i] % MOD);
	printf("%lld\n", ans >> 1);
	return 0;
}