#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

typedef long long ll;

const int N = 1e6 + 5, P = 2e5 + 3, EI = 998244353;

int n, a[N], f[N], t[N], w[N], th[N], ff = 1, tot, rev[N], yg[N];
bool vis[N];
ll ans, g[N];

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = 1ll * res * a % EI;
		a = 1ll * a * a % EI;
		b >>= 1;
	}
	return res;
}

void FFT(int n, int *a, int op)
{
	for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
	yg[n] = qpow(3, (EI - 1) / n * ((n + op) % n));
	for (int i = n >> 1; i; i >>= 1)
		yg[i] = 1ll * yg[i << 1] * yg[i << 1] % EI;
	for (int k = 1; k < n; k <<= 1)
	{
		int x = yg[k << 1];
		for (int i = 0; i < n; i += k << 1)
		{
			int w = 1;
			for (int j = 0; j < k; j++)
			{
				int u = a[i + j], v = 1ll * w * a[i + j + k] % EI;
				a[i + j] = (u + v) % EI; a[i + j + k] = (u - v + EI) % EI;
				w = 1ll * w * x % EI;
			}
		}
	}
	if (op == -1)
	{
		int gg = qpow(n, EI - 2);
		for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * gg % EI;
	}
}

int main()
{
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 0, j = 1; i < P - 1; i++, j = 2ll * j % P) th[j] = i;
	for (int i = 1; i <= n; i++) if (a[i]) f[th[a[i]]]++;
	while (ff < 2 * P - 1) ff <<= 1, tot++;
	for (int i = 0; i < ff; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << tot - 1);
	for (int i = 0; i < P; i++)
	{
		w[i] = f[i];
		if (f[i] > 4000) f[i] = 0, vis[i] = 1;
	}
	FFT(ff, f, 1);
	for (int i = 0; i < ff; i++) f[i] = 1ll * f[i] * f[i] % EI;
	FFT(ff, f, -1);
	for (int i = 0; i < ff; i++) g[i] = f[i];
	for (int i = 0; i < P; i++) if (vis[i])
		for (int j = 0; j < P; j++)
			g[i + j] += 1ll * w[i] * w[j] * (vis[j] ? 1 : 2);
	for (int i = 0, j = 1; i < ff; i++, j = 2ll * j % P) ans += g[i] * j;
	for (int i = 1; i <= n; i++) ans -= 1ll * a[i] * a[i] % P;
	return std::cout << ans / 2 << std::endl, 0;
}
### Prompt

Create a solution in CPP for 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>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

typedef long long ll;

const int N = 1e6 + 5, P = 2e5 + 3, EI = 998244353;

int n, a[N], f[N], t[N], w[N], th[N], ff = 1, tot, rev[N], yg[N];
bool vis[N];
ll ans, g[N];

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = 1ll * res * a % EI;
		a = 1ll * a * a % EI;
		b >>= 1;
	}
	return res;
}

void FFT(int n, int *a, int op)
{
	for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
	yg[n] = qpow(3, (EI - 1) / n * ((n + op) % n));
	for (int i = n >> 1; i; i >>= 1)
		yg[i] = 1ll * yg[i << 1] * yg[i << 1] % EI;
	for (int k = 1; k < n; k <<= 1)
	{
		int x = yg[k << 1];
		for (int i = 0; i < n; i += k << 1)
		{
			int w = 1;
			for (int j = 0; j < k; j++)
			{
				int u = a[i + j], v = 1ll * w * a[i + j + k] % EI;
				a[i + j] = (u + v) % EI; a[i + j + k] = (u - v + EI) % EI;
				w = 1ll * w * x % EI;
			}
		}
	}
	if (op == -1)
	{
		int gg = qpow(n, EI - 2);
		for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * gg % EI;
	}
}

int main()
{
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 0, j = 1; i < P - 1; i++, j = 2ll * j % P) th[j] = i;
	for (int i = 1; i <= n; i++) if (a[i]) f[th[a[i]]]++;
	while (ff < 2 * P - 1) ff <<= 1, tot++;
	for (int i = 0; i < ff; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << tot - 1);
	for (int i = 0; i < P; i++)
	{
		w[i] = f[i];
		if (f[i] > 4000) f[i] = 0, vis[i] = 1;
	}
	FFT(ff, f, 1);
	for (int i = 0; i < ff; i++) f[i] = 1ll * f[i] * f[i] % EI;
	FFT(ff, f, -1);
	for (int i = 0; i < ff; i++) g[i] = f[i];
	for (int i = 0; i < P; i++) if (vis[i])
		for (int j = 0; j < P; j++)
			g[i + j] += 1ll * w[i] * w[j] * (vis[j] ? 1 : 2);
	for (int i = 0, j = 1; i < ff; i++, j = 2ll * j % P) ans += g[i] * j;
	for (int i = 1; i <= n; i++) ans -= 1ll * a[i] * a[i] % P;
	return std::cout << ans / 2 << std::endl, 0;
}
```