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<iostream>
#include<cstring>
#include<cstdio>
#include<complex>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll ;
typedef complex<double> cp;
const int Mod=200003;
const int G=2;
int len,bit;
#define Maxn 600010
int rev[Maxn];
cp A[Maxn];

#define pi acos(-1)
void fft(cp A[],int t){
    for(int i=0;i<len;++i)
    if(rev[i]>i)swap(A[rev[i]],A[i]); 
    for(int i=1;i<len;i<<=1){
        cp wn(cos(pi/i),t*sin(pi/i));
        for(int j=0;j<len;j+=i<<1){
            cp w(1,0);
            for(int k=0;k<i;++k){
                cp x=A[k+j];
                cp y=w*A[k+j+i];
                A[j+k]=x+y;
                A[k+j+i]=x-y;
                w=w*wn;
            }
        }
    }
    if(t==-1)
    for(int i=0;i<len;++i)A[i]/=len;
}

int n;
int g[Maxn],to[Maxn];

int main(){
	g[0]=1;
	for(int i=1;i<Mod-1;++i){
		g[i]=2*g[i-1]%Mod;
		to[g[i]]=i;
	}
	ll Ans=0;
	scanf("%d",&n);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		int tmp=1ll*x*x%Mod;
		Ans-=tmp;
		if(!x)continue;
	    x=to[x];
	    A[x]+=cp(1.0,0.0);
	}
	len=1;bit=0;
	while(len<(Mod-1)*2)len<<=1,bit++;
	for(int i=0;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	fft(A,1);
	for(int i=0;i<len;++i)A[i]=A[i]*A[i];
	fft(A,-1);
	int num=1;
	for(int i=0;i<(Mod-1)*2;++i){
		Ans+=(ll)(A[i].real()+0.5)*num;
		num=2*num%Mod;
	}
	Ans/=2;
	printf("%lld\n",Ans);
    return 0;
}