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 <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
typedef complex<double> base;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false;
const ll mod=200003;

// this is actually C

void fft(vector<base> &a, bool inv)
{
	int n=a.size(), j=0;
	vector<base> roots(n/2);
	for(int i=1; i<n; i++)
	{
		int bit=(n>>1);
		while(j>=bit)
		{
			j-=bit;
			bit>>=1;
		}
		j+=bit;
		if(i<j) swap(a[i],a[j]);
	}
	double ang=2*acos(-1)/n*(inv?-1:1);
	for(int i=0; i<n/2; i++) roots[i]=base(cos(ang*i), sin(ang*i));
	for(int i=2; i<=n; i<<=1)
	{
		int step=n/i;
		for(int j=0; j<n; j+=i)
		{
			for(int k=0; k<i/2; k++)
			{
				base u=a[j+k], v=a[j+k+i/2]*roots[step*k];
				a[j+k]=u+v;
				a[j+k+i/2]=u-v;
			}
		}
	}
	if(inv) for(int i=0; i<n; i++) a[i] /= n;
}

vector<ll> multiply(vector<ll> &v, vector<ll> &w)
{
	vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
	int n=2; while(n<v.size()+w.size()) n<<=1;
	fv.resize(n); fw.resize(n);
	fft(fv,false); fft(fw,false);
	for(int i=0; i<n; i++) fv[i]*=fw[i];
	fft(fv, true); vector<ll> ret(n);
	for(int i=0; i<n; i++) ret[i]=(ll)round(fv[i].real());
	return ret;
}

ll ans, n, g=2;
vector<ll> X, Y;
ll a[222222];
ll cnt[222222];
ll inv[222222];

int main(void)
{
	fio; ll i, x, j, cur=1;
	for(i=0 ; i<=mod-2 ; i++)
	{
		inv[cur]=i;
		cur=(cur*g)%mod;
		if(i!=mod-2) assert(cur!=1);
	}
	cin>>n;
	for(i=1 ; i<=n ; i++)
	{
		cin>>x; a[i]=x;
		if(x==0) continue;
		cnt[inv[x]]++;
	}
	for(i=0 ; i<=mod-2 ; i++) 
	{
		X.push_back(cnt[i]);
		Y.push_back(cnt[i]);
	}
	vector<ll> Z=multiply(X, Y); cur=1;
	for(i=0 ; i<Z.size() ; i++)
	{
		ans+=Z[i]*cur;
		cur=(cur*g)%mod;
	}
	for(i=1 ; i<=n ; i++) ans-=(a[i]*a[i])%mod;
		cout<<ans/2; return 0;
}