#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=555555,mod=200003,g=2;
const double pi=3.141592653589793238;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
inline int qmo(int x){return x+(x>>31)*mod;}
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
struct comp{
	double x,y;
	comp(double xx=0,double yy=0):x(xx),y(yy){}
	comp operator+(const comp &c)const{return comp(x+c.x,y+c.y);}
	comp operator-(const comp &c)const{return comp(x-c.x,y-c.y);}
	comp operator*(const comp &c)const{return comp(x*c.x-y*c.y,x*c.y+y*c.x);}
}A[maxn],Wn[maxn];
int n,a[maxn],id[maxn],pw[maxn],cnt[maxn],lim,l,rev[maxn];
ll cnt2[maxn],ans;
void init(){
	int pr=1;
	FOR(i,0,mod-1){
		id[pr]=i;
		pw[i]=pr;
		pr=1ll*pr*g%mod;
	}
}
void init(int upr){
	for(lim=1,l=0;lim<upr;lim<<=1,l++);
	FOR(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=1;i<lim;i<<=1) FOR(k,0,i-1) Wn[i+k]=comp(cos(pi/i*k),sin(pi/i*k));
}
void DFT(comp *A){
	FOR(i,0,lim-1) if(i<rev[i]) swap(A[i],A[rev[i]]);
	for(int i=1;i<lim;i<<=1){
//		comp Wn(cos(pi/i),sin(pi/i));
//		printf("Wn=(%.5lf,%.5lf)\n",Wn.x,Wn.y);
		for(int j=0;j<lim;j+=i<<1){
//			comp w(1,0);
			FOR(k,0,i-1){
				comp x=A[j+k],y=A[i+j+k]*Wn[i+k];
//				comp x=A[j+k],y=A[i+j+k]*w;
				A[j+k]=x+y;A[i+j+k]=x-y;
//				w=w*Wn;
			}
		}
	}
}
void IDFT(comp *A){
	DFT(A);
	reverse(A+1,A+lim);
	FOR(i,0,lim-1) A[i].x/=lim;
}
int main(){
	init();
	n=read();
	FOR(i,1,n){
		a[i]=read();
		if(a[i]) cnt[id[a[i]]]++;
	}
	FOR(i,0,mod-1) A[i].x=cnt[i];
	init(mod*2);
	DFT(A);
	FOR(i,0,lim-1) A[i]=A[i]*A[i];
	IDFT(A); 
	FOR(i,0,lim-1) cnt2[i%(mod-1)]+=ll(A[i].x+0.5);
	FOR(i,0,mod-1) ans+=cnt2[i]*pw[i];
	FOR(i,1,n) ans-=1ll*a[i]*a[i]%mod;
	ans/=2;
//	FOR(i,0,mod-1) if(cnt2[i]) printf("%d\n",pw[i]);
	printf("%lld\n",ans);
}
### Prompt

Generate 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;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=555555,mod=200003,g=2;
const double pi=3.141592653589793238;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
inline int qmo(int x){return x+(x>>31)*mod;}
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
struct comp{
	double x,y;
	comp(double xx=0,double yy=0):x(xx),y(yy){}
	comp operator+(const comp &c)const{return comp(x+c.x,y+c.y);}
	comp operator-(const comp &c)const{return comp(x-c.x,y-c.y);}
	comp operator*(const comp &c)const{return comp(x*c.x-y*c.y,x*c.y+y*c.x);}
}A[maxn],Wn[maxn];
int n,a[maxn],id[maxn],pw[maxn],cnt[maxn],lim,l,rev[maxn];
ll cnt2[maxn],ans;
void init(){
	int pr=1;
	FOR(i,0,mod-1){
		id[pr]=i;
		pw[i]=pr;
		pr=1ll*pr*g%mod;
	}
}
void init(int upr){
	for(lim=1,l=0;lim<upr;lim<<=1,l++);
	FOR(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=1;i<lim;i<<=1) FOR(k,0,i-1) Wn[i+k]=comp(cos(pi/i*k),sin(pi/i*k));
}
void DFT(comp *A){
	FOR(i,0,lim-1) if(i<rev[i]) swap(A[i],A[rev[i]]);
	for(int i=1;i<lim;i<<=1){
//		comp Wn(cos(pi/i),sin(pi/i));
//		printf("Wn=(%.5lf,%.5lf)\n",Wn.x,Wn.y);
		for(int j=0;j<lim;j+=i<<1){
//			comp w(1,0);
			FOR(k,0,i-1){
				comp x=A[j+k],y=A[i+j+k]*Wn[i+k];
//				comp x=A[j+k],y=A[i+j+k]*w;
				A[j+k]=x+y;A[i+j+k]=x-y;
//				w=w*Wn;
			}
		}
	}
}
void IDFT(comp *A){
	DFT(A);
	reverse(A+1,A+lim);
	FOR(i,0,lim-1) A[i].x/=lim;
}
int main(){
	init();
	n=read();
	FOR(i,1,n){
		a[i]=read();
		if(a[i]) cnt[id[a[i]]]++;
	}
	FOR(i,0,mod-1) A[i].x=cnt[i];
	init(mod*2);
	DFT(A);
	FOR(i,0,lim-1) A[i]=A[i]*A[i];
	IDFT(A); 
	FOR(i,0,lim-1) cnt2[i%(mod-1)]+=ll(A[i].x+0.5);
	FOR(i,0,mod-1) ans+=cnt2[i]*pw[i];
	FOR(i,1,n) ans-=1ll*a[i]*a[i]%mod;
	ans/=2;
//	FOR(i,0,mod-1) if(cnt2[i]) printf("%d\n",pw[i]);
	printf("%lld\n",ans);
}
```