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 flag)
{
  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,root=ModPow(3,(mod-1)/l),div;
    if(flag)root=ModPow(root,mod-2);
    for(int i=0;i<len;i+=l)
    {
      int temp=1;
      rep(j,m)
      {
        div=1l*A[i+j+m]*temp%mod;temp=1l*temp*root%mod;
        A[i+j+m]=ModAdd(A[i+j],mod-div);A[i+j]=ModAdd(A[i+j],div);
      }
    }
  }
  if(flag){flag=ModPow(len,mod-2);rep(i,len){A[i]=1l*A[i]*flag%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(0);rep(i,len){A[i]=1l*A[i]*A[i]%mod;}NTT(1);
  bit=1;rep(i,400004){total+=1l*A[i]*bit;bit=2*bit%MOD;}
  return OUT(total/2),0;
}