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 <cstdio>
#include <cmath>
#include <cstdio>
#include <complex>
#define maxn 2098000
#define eps 0.01
#define Lovelive long long
typedef std::complex<double> C;
const double PI2 = 2.0 * acos(-1);
C coa[maxn], cob[maxn], x[maxn], ax[maxn], temp[maxn];
long long Ans[maxn];

inline int r() {
	int x = 0; char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x;
}

inline int lowbit(int x) {
	return x & -x;
}

void FFT(int n, C *A, C* X) {
	int m = n >> 1;
	for(int step = m; step; step >>= 1) {
		for(int off = 0; off != step; ++off) {
			for(int i = 0, j = 0; j < m; ++i, j += step) {
				C &ta = A[j * 2 + off], tb = X[j] * A[j * 2 + off + step];
				temp[j] = ta + tb, temp[j + m] = ta - tb;
			}
			for(int j = 0; j < n; j += step) A[off + j] = temp[j];
		}
	}
}

void work(int n) {
//	freopen("3803.in", "r", stdin);
//	freopen("out.txt", "w", stdout);
	int m, res;
	m = n;
	res = (n += m + 1);
	while(__builtin_popcount(n) != 1) n += lowbit(n);
	double part = PI2 / n;
	for(int i = 0; i < n; i++) {
		double deg = part * i;
		x[i] = C(cos(deg), sin(deg));
		ax[i] = conj(x[i]);
	}
	FFT(n, coa, x);
	FFT(n, cob, x);
	for(int i = 0; i < n; i++) coa[i] = coa[i] * cob[i];
	FFT(n, coa, ax);
	for(int i = 0; i < res; i++) 
		Ans[i] = (long long)(coa[i].real() / n + eps);
//        printf("%d%c", (int)(coa[i].real() / n + eps), i == res-1 ? '\n' : ' ');
}

#define MOD 200003
#define g 2
int Exp[MOD + 233];
int Pow[MOD + 233];
int a[maxn];
int b[maxn];

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", a + i);
	Pow[0] = 1;
	for(int i = 1, j = 1; i < MOD; ++i) {
		j = j * g % MOD;
		Exp[j] = i;
		Pow[i] = j;
	} 
	for(int i = 1; i <= n; ++i) if(a[i]) ++b[Exp[a[i]]];
	for(int i = 0; i <= MOD; ++i) cob[i] = coa[i] = b[i];
	work(MOD);
	Lovelive ans = 0;
//	for(int i = 0; i <= MOD; ++i) coa[2 * i] -= b[i] * b[i];
	for(int i = 0; i <= MOD; ++i) Ans[2 * i] -= b[i];
	for(int i = 0; i <= 2 * MOD; ++i) ans = ans + (Ans[i] / 2) * Pow[i % (MOD - 1)];
	printf("%lld", ans);
}