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<cstdio>
#include<cmath>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,P=200003;
struct Complex
{
	double x,y;
	inline Complex(const double& X=0,const double& Y=0) { x=X; y=Y; }
	friend inline Complex operator + (const Complex& A,const Complex& B)
	{
		return Complex(A.x+B.x,A.y+B.y);
	}
	friend inline Complex operator - (const Complex& A,const Complex& B)
	{
		return Complex(A.x-B.x,A.y-B.y);
	}
	friend inline Complex operator * (const Complex& A,const Complex& B)
	{
		return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
	}
	inline void operator /= (const double& p)
	{
		x/=p; y/=p;
	}
}b[P<<2]; int n,a[N],g,lg[N],rg[P],cnt,cur; long long ans;
inline int quick_pow(int x,int p,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%P) if (p&1) mul=1LL*mul*x%P; return mul;
}
inline int getroot(CI x=P)
{
	RI i,j; for (i=2;i<=x-2;++i) if ((x-1)%i==0) rg[++cnt]=i;
	for (i=2;;++i)
	{
		bool flag=1; for (j=1;j<=cnt;++j)
		if (quick_pow(i,rg[j])==1) { flag=0; break; }
		if (flag) return i;
	}
}
namespace Poly
{
	const double pi=acos(-1);
	int lim,p,rev[P<<2];
	inline void init(CI n)
	{
		for (lim=1,p=0;lim<=n;lim<<=1,++p);
		for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
	}
	inline void FFT(Complex *f,CI opt)
	{
		RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
		for (i=1;i<lim;i<<=1)
		{
			Complex D(cos(pi/i),sin(pi/i)*opt);
			for (j=0;j<lim;j+=(i<<1))
			{
				Complex W(1,0); for (k=0;k<i;++k,W=W*D)
				{
					Complex x=f[j+k],y=f[i+j+k]*W;
					f[j+k]=x+y; f[i+j+k]=x-y;
				}
			}
		}
		if (!~opt) for (i=0;i<lim;++i) f[i]/=lim;
	}
};
int main()
{
	RI i; for (g=getroot(P),cur=1,i=0;i<P-1;++i,(cur*=g)%=P) lg[cur]=i;
	for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),a[i]&&(b[lg[a[i]]].x+=1.0);
	for (Poly::init(P<<1),Poly::FFT(b,1),i=0;i<Poly::lim;++i) b[i]=b[i]*b[i];
	for (Poly::FFT(b,-1),i=1;i<P;++i) ans+=1LL*i*(long long)(b[lg[i]].x+b[lg[i]+P-1].x+0.5);
	for (i=1;i<=n;++i) ans-=1LL*a[i]*a[i]%P; return printf("%lld",ans>>1LL),0;
}