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<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

ULL mpow(ULL a,ULL i,ULL M) {
 if(i==0) return 1;
 ULL r=mpow(a*a%M,i>>1,M);
 if(i&1) r=r*a%M;
 return r;
}

// NTT WEST
void NTT(vector<ULL>& A,ULL M,ULL g){
 int N=A.size();
 for(int i=0,j=0; j<N; j++){
  if(i<j) swap(A[i],A[j]);
  for(int k=N>>1; k>(i^=k); k>>=1);
 }
 for(int i=1; i<N; i<<=1){
  ULL q=mpow(g,(M-1)/i/2,M);
  ULL qj=1;
  rep(j,i){
   for(int k=j; k<N; k+=i*2){
    ULL l=A[k],r=A[k+i]*qj%M;
    A[k]=(l+r); if(A[k]>=M) A[k]-=M;
    A[k+i]=(l+M-r); if(A[k+i]>=M) A[k+i]-=M;
   }
   qj=qj*q%M;
  }
 }
}

struct Fuse{ ULL M,G; };

// trinitrotoluene EXPLODING!!
vector<ULL> TNT(const vector<ULL>& A,const vector<ULL>& B,Fuse F) {
 int Z=1; while(Z<A.size()+B.size()) Z<<=1;
 vector<ULL> Ax(Z),Bx(Z);
 ULL iZ=mpow(Z,F.M-2,F.M);
 rep(i,Z) Ax[i]=Bx[i]=0;
 rep(i,A.size()) Ax[i]=A[i];
 rep(i,B.size()) Bx[i]=B[i];
 NTT(Ax,F.M,F.G);
 NTT(Bx,F.M,F.G);
 rep(i,Z) Ax[i]=Ax[i]*Bx[i]%F.M;
 NTT(Ax,F.M,mpow(F.G,F.M-2,F.M));
 rep(i,Z) Ax[i]=Ax[i]*iZ%F.M;
 return move(Ax);
}

const Fuse fuse[2] = {{998244353,3},{1107296257,10}};

LL ExtGcd(LL a,LL b,LL& x,LL& y){
 if(b==0){ x=1; y=0; return a; }
 LL g=ExtGcd(b,a%b,y,x);
 y-=a/b*x;
 return g;
}

struct ModEq{
 ULL c1,c2,t1,t2,M;
 ModEq(LL m1,LL m2) {
  LL buf1,buf2;
  ExtGcd(m1,m2,buf1,buf2);
  c1=(buf1+m2)%m2;
  c2=(buf2+m1)%m1;
  t1=m1; t2=m2;
  M=m1*m2;
 }
 ULL operator()(ULL a1, ULL a2) {
  ULL d=a1+(a2+t2-a1)*c1%t2*t1;
  return d;
 }
};

const ULL M=200003;
int N;
int I[M];
vector<ULL> A;
vector<ULL> C[2];

int main() {
 scanf("%d", &N);
 for (int i = 0, j = 1; i < M - 1; i++, j = j * 2 % M) I[j] = i;
 A.resize(M - 1);
 rep(i, N) {
  int a; scanf("%d", &a);
  if (a) A[I[a]]++;
 }
 rep(i, 2) C[i] = TNT(A, A, fuse[i]);
 ModEq X(fuse[0].M, fuse[1].M);
 rep(i, C[0].size()) C[0][i] = X(C[0][i], C[1][i]);
 rep(i, M - 1) C[0][i * 2] -= A[i];
 for (ULL& c : C[0]) c /= 2;

 ULL ans = 0;
 for (int i = 0, j = 1; i < C[0].size(); i++, j = j * 2 % M)
  ans += C[0][i] * j;

 cout<<ans<<endl;

 return 0;
}