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 P = 200003, K = 20, LIM = 1000;
const long long mod = 998244353ll, R1 = 2ll, R2 = 3ll;

template <class T>
void read(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void write(T x) {
	if (x < 0) putchar('-'), write(-x);
	else if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

int n, len = 1;
long long cnt[P], w[K][P << 2], inv[P << 2], ans = 0ll;

long long qpow (long long a, long long b) {
	long long res = 1ll;
	for (; b; b >>= 1, a = a * a % mod) {
		if (b & 1) res =  res * a % mod;
	}
	return res;
}
int bitrev[P << 2];
void ntt_init() {
	while (len < (P << 1)) len <<= 1;
	inv[1] = 1ll;
	for (int i = 2; i <= len; i++) inv[i] = (mod / i) * (mod - inv[mod % i]) % mod;
	for (int i = 0; (1 << i) <= len; i++) {
		w[i][0] = 1ll, w[i][1] = qpow(R2, mod - 1 >> i);
		for (int k = 2; k <= (1 << i); k++) w[i][k] = w[i][k - 1] * w[i][1] % mod;
	}
	bitrev[0] = 0;
	for (int i = 1; i < len; i++) {
		bitrev[i] = bitrev[i >> 1] >> 1;
		if (i & 1) bitrev[i] |= (len >> 1);
	}
}
void ntt (long long *a, int ty) {
	for (int i = 0; i < len; i++) {
		int j = bitrev[i];
		if (j < i) swap(a[i], a[j]);
	}
	for (int i = 1, j = 1; i < len; i <<= 1, j++) {
		for (int k = 0; k < len; k += (i << 1)) {
			for (int l = 0; l < i; l++) {
				long long u = a[k + l], v = a[k + l + i];
				long long rt = w[j][ty > 0 ? l : (i << 1) - l];
				a[k + l] = (u + rt * v) % mod;
				a[k + l + i] = (u + mod * mod - rt * v) % mod;
			}
		}
	}
	if (ty < 0) {
		for (int i = 0; i < len; i++) a[i] = a[i] * inv[len] % mod;
	} 
}

long long vec1[P << 2], vec2[P << 2], vec3[P << 2];
int main () {
	read(n);
	for (int i = 0; i < P; i++) cnt[i] = 0;
	for (int i = 0; i < n; i++) {
		int x;
		read(x);
		ans -= 1ll * x * x % P;
		cnt[x]++;
	}
	ntt_init();
	for (int i = 0; i < len; i++) vec1[i] = vec2[i] = 0;
	for (int i = 0, j = 1; i < P - 1; i++, j = 1ll * j * R1 % P) {
		vec1[i] = cnt[j] / LIM;
		vec2[i] = cnt[j] % LIM;
	}
	
	ntt(vec1, 1), ntt(vec2, 1);
	for (int i = 0; i < len; i++) vec3[i] = 2ll * vec1[i] % mod * vec2[i] % mod;
	for (int i = 0; i < len; i++) vec1[i] = vec1[i] * vec1[i] % mod;
	for (int i = 0; i < len; i++) vec2[i] = vec2[i] * vec2[i] % mod;
	ntt(vec1, -1), ntt(vec2, -1), ntt(vec3, -1);
	
	for (int i = 0, j = 1; i < P - 1; i++, j = 1ll * j * R1 % P) {
		long long res = 0ll;
		res += 1ll * LIM * LIM * (vec1[i] + vec1[i + P - 1]);
		res += 1ll * LIM * (vec3[i] + vec3[i + P - 1]);
		res += vec2[i] + vec2[i + P - 1];
		ans += res * j; 
	}
	ans >>= 1;
	write(ans), putchar('\n'); 
	return 0;
}