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<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed_=(b);i<=_ed_;++i)
#define DREP(i,a,b) for(int i=(a),_ed_=(b);i>=_ed_;--i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)((x).size())
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int P=200003,G=2;
int N,num[P],a[200005];

const double pi=acos(-1.0);
struct cmplx{
    double x,y;
    cmplx(double x=0,double y=0):x(x),y(y){}
    cmplx operator+(const cmplx& o){return cmplx(x+o.x,y+o.y);}
    cmplx operator-(const cmplx& o){return cmplx(x-o.x,y-o.y);}
    cmplx operator*(const cmplx& o){return cmplx(x*o.x-y*o.y,x*o.y+y*o.x);}
    cmplx operator/(int t){return cmplx(x/t,y/t);}
};

int tr[525000];cmplx w[525000];
void DFT(cmplx* f,int n){
    REP(i,0,n-1)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(int len=2,d=1;len<=n;d=len,len<<=1)
	for(int p=0;p<n;p+=len)
	    for(int i=p;i<p+d;++i){
		cmplx t=f[i+d]*w[d+i-p];
		f[i+d]=f[i]-t,f[i]=f[i]+t;
	    }
}

cmplx f[525000],g[525000];
ll F[525000];

int main(){
    //freopen("in.in","r",stdin);
    int t=1;
    REP(i,0,P-2)num[t]=i,t=1ll*t*G%P;
    N=read();ll ans=0;
    REP(i,1,N){
	a[i]=read();
	if(!a[i])continue;
	++f[num[a[i]]].x,++g[num[a[i]]].x;
    }
    int n=1;for(;n<P+P-1;n<<=1);
    REP(i,0,n-1)tr[i]=(tr[i>>1]>>1)|(i&1?(n>>1):0);
    for(int len=2,d=1;len<=n;d=len,len<<=1){
	cmplx e=cmplx(cos(2*pi/len),sin(2*pi/len));
	w[d]=cmplx(1,0);REP(i,1,d-1)w[d+i]=w[d+i-1]*e;
    }
    DFT(f,n),DFT(g,n);
    REP(i,0,n-1)f[i]=f[i]*g[i];
    DFT(f,n);reverse(f+1,f+n);
    REP(i,0,n-1)f[i]=f[i]/n;
    t=1;
    REP(i,0,n-1)F[i]=(f[i].x+0.5);
    REP(i,1,N)if(a[i])--F[num[a[i]]<<1];
    REP(i,0,n-1)F[i]>>=1;
    REP(i,0,P+P-2){
	ans+=1ll*t*F[i];
	t=1ll*t*G%P;
    }
    printf("%lld\n",ans);
    return 0;
}