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>
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
template <typename T> void chkmax(T &x,T y){x<y?x=y:T();}
template <typename T> void chkmin(T &x,T y){x>y?x=y:T();}
template <typename T> void readint(T &x)
{
	x=0;int f=1;char c;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	x*=f;
}
const int MAXN=600005,P=200003,g=2;
const double pi=acos(-1);

int n,a[MAXN],b[MAXN],d[MAXN];
int N,r[MAXN];
struct Complex
{
	double re, im;
	Complex(double _re = 0, double _im = 0)
		{ re = _re, im = _im; }
	Complex operator + (const Complex t) const
		{ return Complex(re + t.re, im + t.im); }
	Complex operator - (const Complex t) const
		{ return Complex(re - t.re, im - t.im); }
	Complex operator * (const Complex t) const
		{ return Complex(re * t.re - im * t.im, re * t.im + im * t.re); }
};
Complex c[MAXN];

void fft(Complex *A,int f){
	for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	for(int i=1;i<N;i<<=1){
		Complex wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<N;j+=(i<<1)){
			Complex w(1,0);
			for(int k=j;k<j+i;k++,w=w*wn){
				Complex x=A[k],y=A[k+i]*w;
				A[k]=x+y; A[k+i]=x-y;
			}
		}
	}
	if(f==-1)for(int i=0;i<N;++i)A[i].re/=N;
}

int main()
{
	#ifdef LOCAL
	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
	#endif
	readint(n);
	d[0]=1;b[1]=0;
	for(int i=1;i<=P-2;++i)d[i]=d[i-1]*g%P,b[d[i]]=i;
	int x;
	for(int i=1;i<=n;++i)
	{
		readint(x);
		if(x)++a[b[x]];
	}
	
	for(N=1;N<=P*2;N<<=1);
	for(int i=1;i<N;++i)r[i]=(r[i>>1]>>1)^((i&1)*(N>>1));
	for(int i=0;i<P;++i)c[i]=Complex(a[i],0);
	fft(c,1);
	for(int i=0;i<N;++i)c[i]=c[i]*c[i];
	fft(c,-1);
	ll ans=0;
	for(int i=0;i<P;++i)ans+=(ll)(c[i].re+c[i+P-1].re+0.5)*d[i];
	for(int i=0;i<P;++i)ans-=1ll*a[i]*d[2*i%(P-1)];
	cout<<ans/2<<endl;
	return 0;
}