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>
#define mp make_pair
#define pb push_back
#define pll pair<LL,LL>
#define pii pair<int,int>
#define y second
#define x first
#define LL long long 
#define MEM(x) memset(x,0,sizeof(x))
using namespace std;
#define N 524288
#define pi acosl(-1)
typedef complex<long double> C;
int n,m,i,t,g[N];
C a[N],b[N];
void FFTinit(){
	for (i=1;i<N;i++) g[i]=g[i>>1]>>1|((i&1)<<18);
}
void FFT(C *a,int f){
	int i,j,k,p;
	for (i=0;i<N;i++)
		if (g[i]>i) swap(a[i],a[g[i]]);
	for (i=1;i<N;i<<=1){
		C e(cos(pi/i),f*sin(pi/i));
		for (j=0;j<N;j+=i<<1){
			C w(1,0);
			for (k=0;k<i;k++,w*=e){
				C x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
}

int mod = 200003;
int root = 2;
LL cnt[200005];
LL ans[410005];
LL f_pow(LL a,LL b){
    LL res=1,temp=a;
    while(b){
        if(b&1)res=res*temp%mod;
        temp=temp*temp%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int vis[200005];
    LL sum=1;
    for(int i = 0;i<mod-1;i++){
        vis[sum]=i;
        sum=sum*root%mod;
    }

    int n;
    scanf("%d",&n);
    vector<int> v;
    for(int i = 0;i<n;i++){
        int x=2;
        scanf("%d",&x);
        if(x){
            v.pb(vis[x]);
            cnt[vis[x]]++;
         //   printf("%d ",vis[x]);
            assert(f_pow(root,vis[x])==x);
        }
    }
 //  printf("\n");
    for(int i = 0;i<200005;i++){
        a[i]=cnt[i];
    }
    FFTinit();
    FFT(a,1);
    for(int i = 0;i<N;i++)a[i]=a[i]*a[i];
    FFT(a,-1);
    LL res=0;

    for(int i = 0;i<400005;i++){
        ans[i%(mod-1)]+=(a[i].real()/N+0.5);
      /*  if(ans[i]){
     //       printf("%d %lld\n",i,ans[i]);
            res+=f_pow(2,i)*ans[i];
        }*/
    }
    for(auto it:v){
        ans[(it*2)%(mod-1)]--;
    }
    for(int i = 0;i<400005;i++){
        ans[i]=ans[i]/2;
        if(ans[i]){
          //  printf("%d %lld\n",i,ans[i]);
            res+=f_pow(2,i)*ans[i];
        }
    }
    printf("%lld\n",res);
}
/*
100
5
5 4
4 2
4 2 3
5 4 2 3 1
*/