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>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define swap(a,b) (a+=b,b=a-b,a-=b)
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,c=getchar();while(c<48||c>57){f^=(c==45),c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?~x+1: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 REV{int val;}rev[524288];
const int mod=998244353,MOD=200003;
int A[524288]={0},B[200004],len=1;
static inline int ModPow(int a,int b){return b?1l*ModPow(1l*a*a%mod,b>>1)*(b&1?a:1)%mod:1;}
static inline int ModAdd(int a,int b){return (a+=b)>=mod?a-mod:a;}
static inline void NTT(int *a,int lim,int inv)
{
  rep(i,len)if(i<rev[i].val)swap(a[i],a[rev[i].val]);
  for(int l=2;l<=len;l<<=1)
  {
    int m=l>>1,g=ModPow(3,(mod-1)/l),d;
    if(inv)g=ModPow(g,mod-2);
    for(int i=0;i<len;i+=l)
      for(int j=i,w=1;j<i+m;++j,w=1l*w*g%mod)
        d=1l*a[j+m]*w%mod,a[j+m]=ModAdd(a[j],mod-d),a[j]=ModAdd(a[j],d);
  }
  if(inv){inv=ModPow(len,mod-2);rep(i,len){a[i]=1l*a[i]*inv%mod;}}
  return;
}
int main(void)
{
  int N=IN(),bit=1,lim=0,to[200003];long total=0;
  rep(i,MOD-2){bit=2*bit%MOD;to[bit]=i+1;}
  rep(i,N){int x=IN();total-=1l*x*x%MOD;while(1<<lim<=(to[x]+10)<<1){lim++;}if(x){B[x]++,A[to[x]]++;}}
  rep(i,MOD){if(B[i+1]>4800){rep(j,MOD){total+=1l*(i+1)*(j+1)%MOD*B[i+1]*B[j+1]*(1+(i!=j));}B[i+1]=A[to[i+1]]=0;}}
  len=1<<lim;rep(i,len){rev[i].val=(rev[i>>1].val>>1)|((i&1)<<lim>>1);}
  NTT(A,lim,0);rep(i,len){A[i]=1l*A[i]*A[i]%mod;}NTT(A,lim,1);
  bit=1;rep(i,400004){total+=1l*A[i]*bit;bit=2*bit%MOD;}
  return OUT(total/2),0;
}