#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2e5 + 123, p = 200003;
int pw[p], f[p], cnt[p];

typedef complex <double> cd;
const int K = 19;
const double PI = acos(-1);
vector <cd> w[K + 1];
int lg[(1 << K) + 1];

void fft(vector <cd> & a, int inv) {
	int n = a.size();
	int j = 0;
	for (int i = 1; i < n; i++) {
		int k = n >> 1;
		for (; j & k; k >>= 1)
			j ^= k;
		j ^= k;
		if (i < j)
			swap(a[i], a[j]);
	}
	cd even, odd;
	for (int len = 2; len <= n; len <<= 1) {
		int m = lg[len];
		for (int i = 0; i < n; i += len) {
			for (int j = 0; j < len / 2; j++) {
				even = a[i + j], odd = a[i + j + len / 2];
				if (inv) {
					even /= 2, odd /= 2;
					odd *= w[m][j == 0 ? 0 : len - j];
				}	else
					odd *= w[m][j];
				a[i + j] = even + odd;
				a[i + j + len / 2] = even - odd;
			}
		}
	}
}

vector <ll> mul(const vector <int> & a, const vector <int> & b) {
	vector <cd> fa(all(a)), fb(all(b));
	int n = 1, need = a.size() + b.size();
	while (n < need)
		n <<= 1;
	fa.resize(n);
	fb.resize(n);
	fft(fa, 0);
	fft(fb, 0);
	for (int i = 0; i < n; i++)
		fa[i] *= fb[i];
	fft(fa, 1);
	vector <ll> res(need - 1);
	for (int i = 0; i < need - 1; i++)
		res[i] = llround(fa[i].real());
	return res;
}

void pre_fft() {
	for (int i = 2; i <= 1 << K; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	for (int i = 0; i <= K; i++) {
		w[i].resize(1 << i);
		double ang = 2 * PI / (1 << i);
		for (int j = 0; j < 1 << i; j++) {
			w[i][j] = cd(cos(j * ang), sin(j * ang));
		}
	}
}

int bp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)
			res = (ll)res * x % p;
		x = (ll)x * x % p;
		y /= 2;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	pre_fft();
	pw[0] = 1;
	f[1] = 0;
	for (int i = 1; i < p; i++) {
		pw[i] = pw[i - 1] * 2 % p;
		f[pw[i]] = i;
	}
	int n;
	cin >> n;
	vector <int> a(n), cnt(p);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 0) continue;
		cnt[f[a[i]]]++;
	}
	vector <int> b = cnt;
	vector <ll> c = mul(cnt, b);
	ll ans = 0;
	for (int i = 0; i < SZ(c); i++)
		ans += (ll)c[i] * bp(2, i);
	for (int i = 0; i < n; i++)
		ans -= (ll)a[i] * a[i] % p;
	cout << ans / 2;
}

### Prompt

Generate a Cpp solution 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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2e5 + 123, p = 200003;
int pw[p], f[p], cnt[p];

typedef complex <double> cd;
const int K = 19;
const double PI = acos(-1);
vector <cd> w[K + 1];
int lg[(1 << K) + 1];

void fft(vector <cd> & a, int inv) {
	int n = a.size();
	int j = 0;
	for (int i = 1; i < n; i++) {
		int k = n >> 1;
		for (; j & k; k >>= 1)
			j ^= k;
		j ^= k;
		if (i < j)
			swap(a[i], a[j]);
	}
	cd even, odd;
	for (int len = 2; len <= n; len <<= 1) {
		int m = lg[len];
		for (int i = 0; i < n; i += len) {
			for (int j = 0; j < len / 2; j++) {
				even = a[i + j], odd = a[i + j + len / 2];
				if (inv) {
					even /= 2, odd /= 2;
					odd *= w[m][j == 0 ? 0 : len - j];
				}	else
					odd *= w[m][j];
				a[i + j] = even + odd;
				a[i + j + len / 2] = even - odd;
			}
		}
	}
}

vector <ll> mul(const vector <int> & a, const vector <int> & b) {
	vector <cd> fa(all(a)), fb(all(b));
	int n = 1, need = a.size() + b.size();
	while (n < need)
		n <<= 1;
	fa.resize(n);
	fb.resize(n);
	fft(fa, 0);
	fft(fb, 0);
	for (int i = 0; i < n; i++)
		fa[i] *= fb[i];
	fft(fa, 1);
	vector <ll> res(need - 1);
	for (int i = 0; i < need - 1; i++)
		res[i] = llround(fa[i].real());
	return res;
}

void pre_fft() {
	for (int i = 2; i <= 1 << K; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	for (int i = 0; i <= K; i++) {
		w[i].resize(1 << i);
		double ang = 2 * PI / (1 << i);
		for (int j = 0; j < 1 << i; j++) {
			w[i][j] = cd(cos(j * ang), sin(j * ang));
		}
	}
}

int bp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)
			res = (ll)res * x % p;
		x = (ll)x * x % p;
		y /= 2;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	pre_fft();
	pw[0] = 1;
	f[1] = 0;
	for (int i = 1; i < p; i++) {
		pw[i] = pw[i - 1] * 2 % p;
		f[pw[i]] = i;
	}
	int n;
	cin >> n;
	vector <int> a(n), cnt(p);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 0) continue;
		cnt[f[a[i]]]++;
	}
	vector <int> b = cnt;
	vector <ll> c = mul(cnt, b);
	ll ans = 0;
	for (int i = 0; i < SZ(c); i++)
		ans += (ll)c[i] * bp(2, i);
	for (int i = 0; i < n; i++)
		ans -= (ll)a[i] * a[i] % p;
	cout << ans / 2;
}

```