#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 4000010
#define mod 200003
#define ll long long
#define eps 1e-2

int n,m,a[maxn],c[maxn],d[maxn];
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
struct comp{
	double x,y;comp(double xx=0,double yy=0):x(xx),y(yy){}
	comp operator +(const comp &B){return comp(x+B.x,y+B.y);}
	comp operator -(const comp &B){return comp(x-B.x,y-B.y);}
	comp operator *(const comp &B){return comp(x*B.x-y*B.y,x*B.y+y*B.x);}
}F[maxn],G[maxn];
int limit,r[maxn];
const double Pi=acos(-1);
void dft(comp *f,int type)
{
	for(int i=1;i<limit;i++)
	if(i<r[i])swap(f[i],f[r[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		comp wn(cos(Pi/mid),type*sin(Pi/mid));
		for(int j=0;j<limit;j+=(mid<<1)){
			comp w(1,0);
			for(int i=0;i<mid;i++,w=w*wn){
				comp x=f[j+i],y=f[j+i+mid]*w;
				f[j+i]=x+y;f[j+i+mid]=x-y;
			}
		}
	}
	if(type==-1)for(int i=0;i<limit;i++)f[i].x/=limit;
}


int main()
{
	scanf("%d",&n);int len=mod-1;
	for(int i=0;i<len;i++)d[i]=ksm(2,i),c[d[i]]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i])F[c[a[i]]].x+=1;
	}
	int lg=0;limit=1;while(limit<=2*len)limit<<=1,lg++;
	for(int i=1;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));
	dft(F,1);for(int i=0;i<limit;i++)F[i]=F[i]*F[i];dft(F,-1);
	
	for(int i=1;i<=n;i++)if(a[i])F[c[a[i]]+c[a[i]]].x-=1;
	ll ans=0;
	for(int i=0;i<limit;i++)ans+=(ll)(F[i].x/2+1e-1)*d[i%len];
	printf("%lld",ans);
}
### Prompt

Please create a solution in Cpp 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 <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 4000010
#define mod 200003
#define ll long long
#define eps 1e-2

int n,m,a[maxn],c[maxn],d[maxn];
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
struct comp{
	double x,y;comp(double xx=0,double yy=0):x(xx),y(yy){}
	comp operator +(const comp &B){return comp(x+B.x,y+B.y);}
	comp operator -(const comp &B){return comp(x-B.x,y-B.y);}
	comp operator *(const comp &B){return comp(x*B.x-y*B.y,x*B.y+y*B.x);}
}F[maxn],G[maxn];
int limit,r[maxn];
const double Pi=acos(-1);
void dft(comp *f,int type)
{
	for(int i=1;i<limit;i++)
	if(i<r[i])swap(f[i],f[r[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		comp wn(cos(Pi/mid),type*sin(Pi/mid));
		for(int j=0;j<limit;j+=(mid<<1)){
			comp w(1,0);
			for(int i=0;i<mid;i++,w=w*wn){
				comp x=f[j+i],y=f[j+i+mid]*w;
				f[j+i]=x+y;f[j+i+mid]=x-y;
			}
		}
	}
	if(type==-1)for(int i=0;i<limit;i++)f[i].x/=limit;
}


int main()
{
	scanf("%d",&n);int len=mod-1;
	for(int i=0;i<len;i++)d[i]=ksm(2,i),c[d[i]]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i])F[c[a[i]]].x+=1;
	}
	int lg=0;limit=1;while(limit<=2*len)limit<<=1,lg++;
	for(int i=1;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));
	dft(F,1);for(int i=0;i<limit;i++)F[i]=F[i]*F[i];dft(F,-1);
	
	for(int i=1;i<=n;i++)if(a[i])F[c[a[i]]+c[a[i]]].x-=1;
	ll ans=0;
	for(int i=0;i<limit;i++)ans+=(ll)(F[i].x/2+1e-1)*d[i%len];
	printf("%lld",ans);
}
```