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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <assert.h>
#include <fstream>

using namespace std;

typedef double db;
typedef long long ll;

const int MOD = 200003;
const db PI = acos(-1);
const int g = 5;

struct Complex
{
	db real,imag;
	Complex (db R = 0,db I = 0)
	{
		real = R;
		imag = I;
	}
	Complex operator + (const Complex &p)const
	{
		return Complex(real + p.real,imag + p.imag);
	}
	Complex operator - (const Complex &p)const
	{
		return Complex(real - p.real,imag - p.imag);
	}
	Complex operator * (const Complex &p)const
	{
		return Complex(real * p.real - imag * p.imag,real * p.imag + imag * p.real);
	}
}A[MOD << 2],wn[2][MOD << 2];

int n,N;
int rev[MOD << 2];

ll ans;

map<int,int> match;

void init(int l)
{
	N = 1;
	while (N < l)
		N <<= 1;
	for (int i = 1;i < N;i++)
		rev[i] = (rev[i >> 1] >> 1) + (i & 1) * (N >> 1);
	int half = N >> 1;
	for (int i = 0;i < half;i++)
	{
		wn[0][half + i] = Complex(cos(PI * i / half),sin(PI * i / half));
		wn[1][half + i] = Complex(cos(PI * i / half),-sin(PI * i / half));
	}
	for (int i = half - 1;i >= 0;i--)
	{
		wn[0][i] = wn[0][i << 1];
		wn[1][i] = wn[1][i << 1];
	}
}

void FFT(Complex *v,bool inv)
{
	for (int i = 0;i < N;i++)
		if (i < rev[i])
			swap(v[i],v[rev[i]]);
	for (int i = 1;i < N;i <<= 1)
		for (int j = 0;j < N;j += (i << 1))
		{
			Complex *l = v + j,*r = v + j + i,*w = wn[inv] + i,A;
			for (int k = 0;k < i;k++,l++,r++,w++)
			{
				A = *w * *r;
				*r = *l - A;
				*l = *l + A;
			}
		}
	if (inv)
	{
		Complex Inv(1.0 / N,0);
		for (int i = 0;i < N;i++)
			v[i] = v[i] * Inv;
	}
}

int main()
{
	scanf("%d",&n);
	int t = 1;
	for (int i = 0;i < MOD - 1;i++)
	{
		match[t] = i;
		(t *= g) %= MOD;
	}
	init(MOD << 1);
	for (int a,i = 1;i <= n;i++)
	{
		scanf("%d",&a);
		if (!a)
		{
			i--;
			n--;
			continue;
		}
		ans -= (ll)a * a % MOD;
		A[match[a]].real++;
	}
	FFT(A,0);
	for (int i = 0;i < N;i++)
		A[i] = A[i] * A[i];
	FFT(A,1);
	t = 1;
	for (int i = 0;i < MOD * 2;i++)
	{
		ans += (ll)(A[i].real + 0.5) * t;
		(t *= g) %= MOD;
	}
	printf("%lld\n",ans / 2);
	return 0;
}