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 char GET(void)
{
  static char buf[1<<15],*ptr=buf,*end=buf;
  if(ptr==end){ptr=buf,end=buf+fread(buf,1,1<<15,stdin);}return *ptr++;
}
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 int IN(void)
{
  int x=0,f=0;char c=GET();while(c<48||c>57){f^=c==45,c=GET();}
  while(c>47&&c<58){x=x*10+c-48,c=GET();}return f?-x:x;
}
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},{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;
}
static inline int Min(const int x,const int y){return x<y?x:y;}
const int Mod=200003,len=524288,bit=19;const double pi=3.141592653589793238462643383;
int rev[600000];
void fft(int t)
{
  for(int i=0;i<len;++i)if(rev[i]>i){SWAPCP(A[rev[i]],A[i]);}
  for(int i=1;i<len;i<<=1)
  {
    complex wn;wn.real=cos(pi/i),wn.imag=t*sin(pi/i);
    for(int j=0;j<len;j+=i<<1)
    {
      complex w;w.real=1;w.imag=0;
      for(int k=0;k<i;++k)
      {
        complex x=A[k+j];
        complex y=Mul(w,A[k+j+i]);
        A[j+k]=Add(x,y);
        A[k+j+i]=Add(x,Minus(y));
        w=Mul(w,wn);
      }
    }
  }
  if(t==-1)for(int i=0;i<len;++i){A[i].real/=len;A[i].imag/=len;}
} 
int main(void)
{
  int n,g[200003],to[200003];
  g[0]=1;
  for(int i=1;i<Mod-1;++i){g[i]=2*g[i-1]%Mod;to[g[i]]=i;}
  long Ans=0;
  if(!scanf("%d",&n))return -1;
  int x;
  for(int i=1;i<=n;++i)
  {
    if(!scanf("%d",&x))return -1;
    Ans-=1l*x*x%Mod;
    if(!x)continue;
    x=to[x];
    A[x].real+=1.0;
    A[x].imag=0.0;
  }
  for(int i=0;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
  fft(1);
  for(int i=0;i<len;++i)A[i]=Mul(A[i],A[i]);
  fft(-1);
  int num=1%Mod;
  for(int i=0;i<400004;++i){Ans+=(long)(A[i].real+0.5)*num;num=2*num%Mod;}
  return printf("%ld\n",Ans/2),0;
}