#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

#define P 200003
#define N (P * 4 + 400)
#define M 998244353
#define ROOT 3
#define ll long long

int power(int x, int y, int m) {
	int ans = 1;
	for (; y; y >>= 1, x = (ll)x * x % m)
		if (y & 1)
			ans = (ll)ans * x % m;
	return ans;
}
int power(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = (ll)x * x % M)
		if (y & 1)
			ans = (ll)ans * x % M;
	return ans;
}
int limit(int n) {
	int ans = 0;
	for (int i = 1; i < n; i <<= 1)
		ans++;
	return ans;
}
int inv_buf[N << 1], *inv[30], *ptr = inv_buf;
void ntt(int *a, int lim, int flag) {
	int n = 1 << lim;
	if (!inv[lim]) {
		inv[lim] = ptr, ptr += n;
		for (int i = 0; i < n; i++)
			inv[lim][i] = inv[lim][i >> 1] >> 1 | (i & 1 ? n >> 1 : 0);
	}
	for (int i = 0; i < n; i++)
		if (i < inv[lim][i])
			swap(a[i], a[inv[lim][i]]);
	for (int m = 1, k = 2; m < n; m <<= 1, k <<= 1) {
		ll omega = power(ROOT, (M - 1) + flag * (M - 1) / k);
		for (int j = 0; j < n; j += k)
			for (int i = j, omg = 1; i < (j | m); i++, omg = omg * omega % M) {
				int tmp = (ll)omg * a[i | m] % M;
				a[i | m] = (M + a[i] - tmp) % M;
				a[i] = (a[i] + tmp) % M;
			}
	}
	if (flag == -1) {
		ll inv = power(n, M - 2);
		for (int i = 0; i < n; i++)
			a[i] = inv * a[i] % M;
	}
}

int buc[N], lg[N];
int a[N], b[N], q = sqrt(P);
int c[N], d[N], e[N];
ll f[N];

int main() {
	//freopen("ntt.in", "r", stdin);
	lg[1] = 0;
	for (int i = 2, j = 1; i != 1; i = i * 2 % P, j++)
		lg[i] = j;
	int n;
	scanf("%d", &n);
	ll ans = 0;
	for (int i = 1, a; i <= n; i++) {
		scanf("%d", &a);
		if (!a)
			continue;
		ans -= (ll)a * a % P;
		buc[lg[a]]++;
	}
	for (int i = 0; i < P; i++) {
		a[i] = buc[i] / q;
		b[i] = buc[i] % q;
	}
	int lim = limit(P * 2);
	ntt(a, lim, 1);
	ntt(b, lim, 1);
	for (int i = 0; i < (1 << lim); i++) {
		c[i] = (ll)a[i] * a[i] % M;
		d[i] = (ll)a[i] * b[i] * 2 % M;
		e[i] = (ll)b[i] * b[i] % M;
	}
	ntt(c, lim, -1);
	ntt(d, lim, -1);
	ntt(e, lim, -1);
	for (int i = 0; i < P * 2; i++)
		f[i] = e[i] + (ll)d[i] * q + (ll)c[i] * q * q;
	for (int i = 0; i < P - 1; i++)
		f[i] += f[i + P - 1];
	
	for (int i = 0; i < P - 1; i++)
		if (f[i])
			ans += (ll)f[i] * power(2, i, P);
	printf("%lld\n", ans / 2);
}

### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

#define P 200003
#define N (P * 4 + 400)
#define M 998244353
#define ROOT 3
#define ll long long

int power(int x, int y, int m) {
	int ans = 1;
	for (; y; y >>= 1, x = (ll)x * x % m)
		if (y & 1)
			ans = (ll)ans * x % m;
	return ans;
}
int power(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = (ll)x * x % M)
		if (y & 1)
			ans = (ll)ans * x % M;
	return ans;
}
int limit(int n) {
	int ans = 0;
	for (int i = 1; i < n; i <<= 1)
		ans++;
	return ans;
}
int inv_buf[N << 1], *inv[30], *ptr = inv_buf;
void ntt(int *a, int lim, int flag) {
	int n = 1 << lim;
	if (!inv[lim]) {
		inv[lim] = ptr, ptr += n;
		for (int i = 0; i < n; i++)
			inv[lim][i] = inv[lim][i >> 1] >> 1 | (i & 1 ? n >> 1 : 0);
	}
	for (int i = 0; i < n; i++)
		if (i < inv[lim][i])
			swap(a[i], a[inv[lim][i]]);
	for (int m = 1, k = 2; m < n; m <<= 1, k <<= 1) {
		ll omega = power(ROOT, (M - 1) + flag * (M - 1) / k);
		for (int j = 0; j < n; j += k)
			for (int i = j, omg = 1; i < (j | m); i++, omg = omg * omega % M) {
				int tmp = (ll)omg * a[i | m] % M;
				a[i | m] = (M + a[i] - tmp) % M;
				a[i] = (a[i] + tmp) % M;
			}
	}
	if (flag == -1) {
		ll inv = power(n, M - 2);
		for (int i = 0; i < n; i++)
			a[i] = inv * a[i] % M;
	}
}

int buc[N], lg[N];
int a[N], b[N], q = sqrt(P);
int c[N], d[N], e[N];
ll f[N];

int main() {
	//freopen("ntt.in", "r", stdin);
	lg[1] = 0;
	for (int i = 2, j = 1; i != 1; i = i * 2 % P, j++)
		lg[i] = j;
	int n;
	scanf("%d", &n);
	ll ans = 0;
	for (int i = 1, a; i <= n; i++) {
		scanf("%d", &a);
		if (!a)
			continue;
		ans -= (ll)a * a % P;
		buc[lg[a]]++;
	}
	for (int i = 0; i < P; i++) {
		a[i] = buc[i] / q;
		b[i] = buc[i] % q;
	}
	int lim = limit(P * 2);
	ntt(a, lim, 1);
	ntt(b, lim, 1);
	for (int i = 0; i < (1 << lim); i++) {
		c[i] = (ll)a[i] * a[i] % M;
		d[i] = (ll)a[i] * b[i] * 2 % M;
		e[i] = (ll)b[i] * b[i] % M;
	}
	ntt(c, lim, -1);
	ntt(d, lim, -1);
	ntt(e, lim, -1);
	for (int i = 0; i < P * 2; i++)
		f[i] = e[i] + (ll)d[i] * q + (ll)c[i] * q * q;
	for (int i = 0; i < P - 1; i++)
		f[i] += f[i + P - 1];
	
	for (int i = 0; i < P - 1; i++)
		if (f[i])
			ans += (ll)f[i] * power(2, i, P);
	printf("%lld\n", ans / 2);
}

```