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<stdio.h>
#include<string.h>
#include<math.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define SWAPCP(a,b) (a=Add(a,b),b=Add(a,Minus(b)),a=Add(a,Minus(b)))
typedef struct complex complex;
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline void OUT(long a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
struct complex{double real,imag;}A[524288]={{0},{0}};
static inline complex Add(complex x,complex y){complex z;z.real=x.real+y.real;z.imag=x.imag+y.imag;return z;}
static inline complex Minus(complex x){x.real=-x.real;x.imag=-x.imag;return x;}
static inline complex Mul(complex x,complex y)
{
  complex z;z.real=x.real*y.real-x.imag*y.imag;
  z.imag=x.real*y.imag+x.imag*y.real;return z;
}
const int MOD=200003,len=524288,bit=19;
const double pi=3.141592653589793238462643383;
int rev[524288];
static inline void FFT(int t)
{
  rep(i,len)if(rev[i]>i){SWAPCP(A[rev[i]],A[i]);}
  for(int i=1;i<len;i<<=1)
  {
    complex v;v.real=cos(pi/i),v.imag=t*sin(pi/i);
    for(int j=0;j<len;j+=i<<1)
    {
      complex w;w.real=1;w.imag=0;
      rep(k,i)
      {
        complex x=A[k+j],y=Mul(w,A[k+j+i]);
        A[k+j]=Add(x,y);A[k+j+i]=Add(x,Minus(y));
        w=Mul(v,w);
      }
    }
  }
  if(t==-1)rep(i,len){A[i].real/=len;A[i].imag/=len;}
} 
int main(void)
{
  int N,temp=1,to[200003];long sum=0;
  rep(i,MOD-2){temp=2*temp%MOD;to[temp]=i+1;}
  if(!scanf("%d",&N))return -1;
  rep(i,N)
  {
    int x;if(!scanf("%d",&x))return -1;
    sum-=1l*x*x%MOD;
    if(!x)continue;
    x=to[x];A[x].real+=1.0;A[x].imag=0;
  }
  rep(i,len){rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));}
  FFT(1);rep(i,len){A[i]=Mul(A[i],A[i]);}FFT(-1);
  temp=1%MOD;rep(i,400004){sum+=(long)(A[i].real+0.5)*temp;temp=2*temp%MOD;}
  return OUT(sum/2),0;
}