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;

typedef complex <long double> com;
const int P = 200003, len = 1 << 19;
int n;
com c[len];
int p[P], seq[len];
void fft(com a[], const char &flag);

int main() {
	for (int i = 2, j = 1; i != 1; i = i << 1 >= P ? (i << 1) - P : i << 1, ++j)
		p[i] = j;
	for (int i = 1; i < len; ++i)
		seq[i] = seq[i >> 1] >> 1 | (i & 1) << 18;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int a; scanf("%d", &a);
		if (a != 0)
			c[p[a]] += 1, ans -= 1ll * a * a % P;
	}
	fft(c, 1);
	for (int i = 0; i < len; ++i)
		c[i] = c[i] * c[i] / (long double)(len);
	fft(c, -1);
	for (int i = 0, j = 1; i < len; ++i, j <<= 1) {
		if (j >= P)
			j -= P;
		ans += j * (long long)(c[i].real() + 0.5);
	}
	printf("%lld\n", ans >> 1);
	return 0;
}

void fft(com a[], const char &flag) {
	for (int i = 0; i < len; ++i)
		if (i < seq[i])
			swap(a[i], a[seq[i]]);
	for (int i = 0; 1 << i < len; ++i) {
		const com wn(cos(M_PI / (1 << i)), flag * sin(M_PI / (1 << i)));
		for (int j = 0; j < len; j += 1 << i + 1) {
			com w(1, 0);
			for (int k = 0; k < 1 << i; ++k, w *= wn) {
				com x = a[j + k], y = w * a[j + k + (1 << i)];
				a[j + k] = x + y;
				a[j + k + (1 << i)] = x - y;
			}
		}
	}
	return;
}