#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
inline int read()
{
    int s=0,f=1; char ch=getchar();
    while(!isdigit(ch) && ch!='-')ch=getchar();
    if(ch=='-')ch=getchar(),f=-1;
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return ~f?s:-s;
}


struct Complex {
	double a,b;
	Complex(double x=0,double y=0) {
		a=x;
		b=y;
	}
};

inline Complex operator +(Complex x,Complex y) {
	return Complex(x.a+y.a,x.b+y.b);
}
inline Complex operator -(Complex x,Complex y) {
	return Complex(x.a-y.a,x.b-y.b);
}
inline Complex operator *(Complex x,Complex y) {
	return Complex(x.a*y.a-x.b*y.b,x.a*y.b+y.a*x.b);
}
inline Complex operator /(Complex x,int y) {
	return Complex(x.a/y,x.b/y);
}

const int maxn=3e6+20;

int rev[maxn];
Complex a[maxn],b[maxn];
Complex st[maxn];
int top;

const double Pi=acos(-1);

inline void FFT(Complex *p,int n,int op) {
	int l=0;
	while((1<<l)<n)l++;
	REP(i,1,n-1)rev[i]=(rev[i>>1]>>1) | ((i&1)<<l-1);
	REP(i,1,n-1)if(i<rev[i])swap(p[i],p[rev[i]]);
	for(int i=1; i<n; i<<=1) {
		Complex w=Complex(cos(Pi/i),sin(Pi/i)*op);
		st[0]=Complex(1,0);
		REP(j,1,i-1)st[j]=st[j-1]*w;
		for(int j=0; j<n; j+=i<<1)
			for(int k=0; k<i; k++) {
				Complex x=p[j+k],y=p[i+j+k]*st[k];
				p[j+k]=x+y;
				p[i+j+k]=x-y;
			}
	}
	if(op==-1) {
		REP(i,0,n-1)p[i]=p[i]/n;
	}
}

const int g=2; 
const int mod=200003;

int id[maxn];
int fan[maxn];

int f[maxn];
int A[maxn];
ll num[maxn];

int main()
{
    int n=read();
    id[0]=1; fan[1]=0;
    REP(i,1,mod-2)id[i]=(id[i-1]*2)%mod,fan[id[i]]=i;
    fan[0]=0;
    REP(i,1,n)
    {
	int x=read(); A[i]=x;
	if(x)f[fan[x]]++;
    }
    REP(i,0,mod-1)a[i].a=f[i],b[i].a=f[i];
    int N=1; while(N<=mod*2-2)N<<=1;
    FFT(a,N,1); FFT(b,N,1);
    REP(i,0,N-1)a[i]=a[i]*b[i];
    FFT(a,N,-1);
    REP(i,0,N-1)
    {
	num[i]=(ll)floor(a[i].a+0.5);
    }
    REP(i,mod-1,N-1)num[i%(mod-1)]+=num[i];
    ll ans=0;
    REP(i,0,mod-2)ans+=num[i]*id[i];
    REP(i,1,n)ans-=(ll)A[i]*A[i]%mod;
    ans/=2;
    printf("%lld\n",ans);
    return 0;
}

### Prompt

Your challenge is to write a cpp solution to 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>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
inline int read()
{
    int s=0,f=1; char ch=getchar();
    while(!isdigit(ch) && ch!='-')ch=getchar();
    if(ch=='-')ch=getchar(),f=-1;
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return ~f?s:-s;
}


struct Complex {
	double a,b;
	Complex(double x=0,double y=0) {
		a=x;
		b=y;
	}
};

inline Complex operator +(Complex x,Complex y) {
	return Complex(x.a+y.a,x.b+y.b);
}
inline Complex operator -(Complex x,Complex y) {
	return Complex(x.a-y.a,x.b-y.b);
}
inline Complex operator *(Complex x,Complex y) {
	return Complex(x.a*y.a-x.b*y.b,x.a*y.b+y.a*x.b);
}
inline Complex operator /(Complex x,int y) {
	return Complex(x.a/y,x.b/y);
}

const int maxn=3e6+20;

int rev[maxn];
Complex a[maxn],b[maxn];
Complex st[maxn];
int top;

const double Pi=acos(-1);

inline void FFT(Complex *p,int n,int op) {
	int l=0;
	while((1<<l)<n)l++;
	REP(i,1,n-1)rev[i]=(rev[i>>1]>>1) | ((i&1)<<l-1);
	REP(i,1,n-1)if(i<rev[i])swap(p[i],p[rev[i]]);
	for(int i=1; i<n; i<<=1) {
		Complex w=Complex(cos(Pi/i),sin(Pi/i)*op);
		st[0]=Complex(1,0);
		REP(j,1,i-1)st[j]=st[j-1]*w;
		for(int j=0; j<n; j+=i<<1)
			for(int k=0; k<i; k++) {
				Complex x=p[j+k],y=p[i+j+k]*st[k];
				p[j+k]=x+y;
				p[i+j+k]=x-y;
			}
	}
	if(op==-1) {
		REP(i,0,n-1)p[i]=p[i]/n;
	}
}

const int g=2; 
const int mod=200003;

int id[maxn];
int fan[maxn];

int f[maxn];
int A[maxn];
ll num[maxn];

int main()
{
    int n=read();
    id[0]=1; fan[1]=0;
    REP(i,1,mod-2)id[i]=(id[i-1]*2)%mod,fan[id[i]]=i;
    fan[0]=0;
    REP(i,1,n)
    {
	int x=read(); A[i]=x;
	if(x)f[fan[x]]++;
    }
    REP(i,0,mod-1)a[i].a=f[i],b[i].a=f[i];
    int N=1; while(N<=mod*2-2)N<<=1;
    FFT(a,N,1); FFT(b,N,1);
    REP(i,0,N-1)a[i]=a[i]*b[i];
    FFT(a,N,-1);
    REP(i,0,N-1)
    {
	num[i]=(ll)floor(a[i].a+0.5);
    }
    REP(i,mod-1,N-1)num[i%(mod-1)]+=num[i];
    ll ans=0;
    REP(i,0,mod-2)ans+=num[i]*id[i];
    REP(i,1,n)ans-=(ll)A[i]*A[i]%mod;
    ans/=2;
    printf("%lld\n",ans);
    return 0;
}

```