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 <cstdio>
#include <vector>
#include <cmath>
const double pi = acos(-1);
int TC, N, M, W, NK, ref[200003], cnt[200003], L, p[524288];
long long ans[200003];
long long POWER(long long a, long long b, long long c)
{
	long long r = 1;
	for (; b; b >>= 1)
	{
		if (b & 1)
			r = r * a % c;
		a = a * a % c;
	}
	return r;
}
void NK_MAKE()
{
	std::vector < int > V;
	int tmp = M - 1;
	for (int i = 2; i * i <= tmp; i++)
		if (tmp % i == 0)
		{
			V.push_back((M - 1) / i);
			do tmp /= i; while (tmp % i == 0);
		}
	if (tmp > 1)
		V.push_back((M - 1) / tmp);
	NK = 0;
	bool ok;
	do
	{
		NK++;
		ok = true;
		for (std::vector < int >::iterator i = V.begin(); ok && i != V.end(); i++)
			if (POWER(NK, *i, M) == 1)
				ok = false;
	}
	while (!ok);
}
struct com
{
	double x, y;
	friend inline com operator + (const com &a, const com &b)
	{
		return (com) { a.x + b.x, a.y + b.y };
	}
	friend inline com operator - (const com &a, const com &b)
	{
		return (com) { a.x - b.x, a.y - b.y };
	}
	friend inline com operator * (const com &a, const com &b)
	{
		return (com) { a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x };
	}
}
a[524288];
void FFT(com *a, int f = 1)
{
	if (f == 1)
		for (int i = 1; i < L; i++)
			p[i] = i & 1 ? p[i - 1] | L >> 1 : p[i >> 1] >> 1;
	for (int i = 0; i < L; i++)
		if (i < p[i])
			std::swap(a[i], a[p[i]]);
	for (int i = 1; i < L; i <<= 1)
	{
		com w, wn = (com) { cos(pi / i), sin(pi / i) * f }, x, y;
		for (int j = 0; j < L; j += i + i)
		{
			w = (com) { 1, 0 };
			for (int k = j; k < j + i; k++)
			{
				x = a[k];
				y = a[k + i] * w;
				a[k] = x + y;
				a[k + i] = x - y;
				w = w * wn;
			}
		}
	}
	if (f == -1)
		for (int i = 0; i < L; i++)
			a[i].x /= L;
}
int main()
{
		scanf("%d", &N);
		M = 200003;
		NK_MAKE();
		for (int i = 0, j = 1; i < M - 1; i++, j = j * NK % M)
			ref[j] = i;
		for (int i = 0; i < M; i++)
		{
			cnt[i] = 0;
			ans[i] = 0;
		}
		for (int i = 0, x; i < N; i++)
		{
			scanf("%d", &x);
			cnt[x % M]++;
		}
		L = 1;
		while (L <= M + M - 4)
			L <<= 1;
		for (int i = 0, w = 1; i < M - 1; i++, w = w * NK % M)
			a[i] = (com) { double(cnt[w]), 0 };
		for (int i = M - 1; i < L; i++)
			a[i] = (com) { 0, 0 };
		FFT(a);
		for (int i = 0; i < L; i++)
			a[i] = a[i] * a[i];
		FFT(a, -1);
		for (int i = 0, w = 1; i < L; i++, w = w * NK % M)
			ans[w] += (long long)(a[i].x + 0.5);
		ans[0] = (long long)N * N - (long long)(N - cnt[0]) * (N - cnt[0]);
		for (int i = 0; i < M; i++)
			ans[(long long)i * i % M] -= cnt[i];
		long long Ans = 0;
		for (int i = 0; i < M; i++)
			Ans += i * ans[i] >> 1;
		printf("%lld\n", Ans);
	return 0;
}