#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100,P=200003;
const double pi=acos(-1);
int n,a[N],f[P],p[P];
int len,rev[P*4];
struct com
{
	long double real,ima;
}g[P*4];
com operator+(com a,com b){return(com){a.real+b.real,a.ima+b.ima};}
com operator-(com a,com b){return(com){a.real-b.real,a.ima-b.ima};}
com operator*(com a,com b){return(com){a.real*b.real-a.ima*b.ima,a.real*b.ima+b.real*a.ima};}
inline void change(int len)
{
	for (int i=0;i<len;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if (i&1) rev[i]|=len>>1;
	}
}
inline void fft(com y[],int len,int v)
{
	for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
	for (int i=2;i<=len;i<<=1)
	{
		com step=(com){cos(2.0*pi/i),sin(v*2.0*pi/i)};
		for (int j=0;j<len;j+=i)
		{
			com x=(com){1.0,0};
			for (int k=j;k<j+i/2;k++)
			{
				com a=y[k],b=x*y[k+i/2];
				y[k]=a+b,y[k+i/2]=a-b;
				x=x*step;
			}
		}
	}
	if (v==-1) for (int i=0;i<len;i++) y[i].real/=1.0*len;
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	f[1]=0;
	int x=1;
	for (int i=1;i<P-1;i++) x=(x+x)%P,f[x]=i;
	p[0]=1;
	for (int i=1;i<P-1;i++) p[i]=(p[i-1]+p[i-1])%P;
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]].real+=1;
	len=1;
	while (len<P+P) len<<=1;
	change(len);
	fft(g,len,1);
	for (int i=0;i<len;i++) g[i]=g[i]*g[i];
	fft(g,len,-1);
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]*2].real-=1;
	int ans=0;
	for (int i=0;i<len;i++) ans+=p[i%(P-1)]*((int)(g[i].real+0.5)/2);
	printf("%lld\n",ans);
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
#define int long long
using namespace std;
const int N=200100,P=200003;
const double pi=acos(-1);
int n,a[N],f[P],p[P];
int len,rev[P*4];
struct com
{
	long double real,ima;
}g[P*4];
com operator+(com a,com b){return(com){a.real+b.real,a.ima+b.ima};}
com operator-(com a,com b){return(com){a.real-b.real,a.ima-b.ima};}
com operator*(com a,com b){return(com){a.real*b.real-a.ima*b.ima,a.real*b.ima+b.real*a.ima};}
inline void change(int len)
{
	for (int i=0;i<len;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if (i&1) rev[i]|=len>>1;
	}
}
inline void fft(com y[],int len,int v)
{
	for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
	for (int i=2;i<=len;i<<=1)
	{
		com step=(com){cos(2.0*pi/i),sin(v*2.0*pi/i)};
		for (int j=0;j<len;j+=i)
		{
			com x=(com){1.0,0};
			for (int k=j;k<j+i/2;k++)
			{
				com a=y[k],b=x*y[k+i/2];
				y[k]=a+b,y[k+i/2]=a-b;
				x=x*step;
			}
		}
	}
	if (v==-1) for (int i=0;i<len;i++) y[i].real/=1.0*len;
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	f[1]=0;
	int x=1;
	for (int i=1;i<P-1;i++) x=(x+x)%P,f[x]=i;
	p[0]=1;
	for (int i=1;i<P-1;i++) p[i]=(p[i-1]+p[i-1])%P;
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]].real+=1;
	len=1;
	while (len<P+P) len<<=1;
	change(len);
	fft(g,len,1);
	for (int i=0;i<len;i++) g[i]=g[i]*g[i];
	fft(g,len,-1);
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]*2].real-=1;
	int ans=0;
	for (int i=0;i<len;i++) ans+=p[i%(P-1)]*((int)(g[i].real+0.5)/2);
	printf("%lld\n",ans);
}

```