#include <cstdio>
#include <vector>
#include <complex>
using namespace std;
const int mod = 200003;
const int N = 1 << 19;
const double pi = atan(1.) * 4;
typedef complex<double> C;
int b[mod], v[mod], f[mod], g[N];
long long r[mod];
C c[N], w[N];
void init() {
	for (int i = 0; i < N; i++) {
		w[i] = polar(1., 2 * pi * i / N);
	}
}
void fft(C *a, int inv = 0) {
	for (int i = 1, j = 0; i < N - 1; i++) {
		int s = N;
		do {
			s >>= 1;
			j ^= s;
		} while (~j & s);
		if (i < j) swap(a[i], a[j]);
	}
	for (int i = 2; i <= N; i *= 2) {
		int h = i / 2, inc = N / i;
		if (inv) inc = N - inc;
		for (int j = 0; j < N; j += i) {
			int wi = 0;
			for (int k = 0; k < h; k++) {
				C x = a[j+k], y = a[j+k+h] * w[wi];
				a[j+k] = x + y;
				a[j+k+h] = x - y;
				wi = (wi + inc) & (N - 1);
			}
		}
	}
	if (inv) {
		for (int i = 0; i < N; i++) {
			a[i] /= N;
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	long long x = 2;
	b[1] = 0;
	for (int i = 1; i < mod - 1; i++) {
		b[x] = i;
		v[i] = x;
		x = x * 2 % mod;
	}
	v[0] = 1;
	for (int i = 0; i < n; i++) {
		int x; 
		scanf("%d", &x);
		if (x) f[b[x]]++;
	}
	for (int i = 0; i < mod; i++) {
		c[i] = f[i];
		r[(i+i)%(mod-1)] -= f[i];
	}
	init();
	fft(c);
	for (int i = 0; i < N; i++) {
		c[i] = c[i] * c[i];
	}
	fft(c, 1);
	for (int i = 0; i < N; i++) {
		long long x = real(c[i]) + 0.5;
		r[i%(mod-1)] += x;
	}
	long long ans = 0;
	for (int i = 0; i < mod - 1; i++) {
		ans += r[i] * v[i];
	}
	printf("%lld\n", ans / 2);
	return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <cstdio>
#include <vector>
#include <complex>
using namespace std;
const int mod = 200003;
const int N = 1 << 19;
const double pi = atan(1.) * 4;
typedef complex<double> C;
int b[mod], v[mod], f[mod], g[N];
long long r[mod];
C c[N], w[N];
void init() {
	for (int i = 0; i < N; i++) {
		w[i] = polar(1., 2 * pi * i / N);
	}
}
void fft(C *a, int inv = 0) {
	for (int i = 1, j = 0; i < N - 1; i++) {
		int s = N;
		do {
			s >>= 1;
			j ^= s;
		} while (~j & s);
		if (i < j) swap(a[i], a[j]);
	}
	for (int i = 2; i <= N; i *= 2) {
		int h = i / 2, inc = N / i;
		if (inv) inc = N - inc;
		for (int j = 0; j < N; j += i) {
			int wi = 0;
			for (int k = 0; k < h; k++) {
				C x = a[j+k], y = a[j+k+h] * w[wi];
				a[j+k] = x + y;
				a[j+k+h] = x - y;
				wi = (wi + inc) & (N - 1);
			}
		}
	}
	if (inv) {
		for (int i = 0; i < N; i++) {
			a[i] /= N;
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	long long x = 2;
	b[1] = 0;
	for (int i = 1; i < mod - 1; i++) {
		b[x] = i;
		v[i] = x;
		x = x * 2 % mod;
	}
	v[0] = 1;
	for (int i = 0; i < n; i++) {
		int x; 
		scanf("%d", &x);
		if (x) f[b[x]]++;
	}
	for (int i = 0; i < mod; i++) {
		c[i] = f[i];
		r[(i+i)%(mod-1)] -= f[i];
	}
	init();
	fft(c);
	for (int i = 0; i < N; i++) {
		c[i] = c[i] * c[i];
	}
	fft(c, 1);
	for (int i = 0; i < N; i++) {
		long long x = real(c[i]) + 0.5;
		r[i%(mod-1)] += x;
	}
	long long ans = 0;
	for (int i = 0; i < mod - 1; i++) {
		ans += r[i] * v[i];
	}
	printf("%lld\n", ans / 2);
	return 0;
}

```