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>
#define pi 3.1415926535897932384626
using namespace std;

struct P{
  int x,y;
  bool operator < (const P &a )const{
    if(x!=a.x) return x<a.x;
    return y<a.y;
    
  };
};

int a,b,c,d,i,n,m,e,k,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[222221];
int l[1];
int ss[1];

long long x,y,z,mod=1000000007,hf=(mod+1)/2;

//string r;
char r[1];
vector<int> v;
P u[1];

queue<int> q;
//set<int> s;
stack<int> s;
map<int,int> p;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//rng()
bool as(P a,P b)
{
  return a.y<b.y;
}

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384626
typedef complex<double> base;
 
void fft(vector <base> &a, bool invert)
{
    int n = sz(a);
    for (int i=1,j=0;i<n;i++){
        int bit = n >> 1;
        for (;j>=bit;bit>>=1) j -= bit;
        j += bit;
        if (i < j) swap(a[i],a[j]);
    }
    for (int len=2;len<=n;len<<=1){
        double ang = 2*pi/len*(invert?-1:1);
        base wlen(cos(ang),sin(ang));
        for (int i=0;i<n;i+=len){
            base w(1);
            for (int j=0;j<len/2;j++){
                base u = a[i+j], v = a[i+j+len/2]*w;
                a[i+j] = u+v;
                a[i+j+len/2] = u-v;
                w *= wlen;
            }
        }
    }
    if (invert){
        for (int i=0;i<n;i++) a[i] /= n;
    }
}
 
void multiply(const vector<long long> &a,const vector<long long> &b,vector<long long> &res)
{
    vector <base> fa(all(a)), fb(all(b));
    int n = 1;
    while (n < max(sz(a),sz(b))) n <<= 1;
    fa.resize(n); fb.resize(n);
    fft(fa,false); fft(fb,false);
    for (int i=0;i<n;i++) fa[i] *= fb[i];
    fft(fa,true);
    res.resize(n);
    for (int i=0;i<n;i++) res[i] = (long long)(fa[i].real()+(fa[i].real()>0?0.5:-0.5));
}

int main()
{
  scanf("%d",&a);
  mod=200003;
  long long p=2;
  e=1;
  for(int t=0;t<mod-1;t++)
  {
    o[e]=t;
    e*=p;
    e%=mod;
  }
  long long po[444444];
  po[0]=1;
  for(int t=1;t<=mod*2;t++)
    po[t]=po[t-1]*2%mod;
  vector<long long> v1,v2,v;
  v1.resize(mod*2);
  v2.resize(mod*2);
  x=0;
  for(int t=1;t<=a;t++)
  {
    scanf("%d",&n);
    if(n==0) continue;
    v1[o[n]]++;
    v2[o[n]]++;
    //printf("%d ",o[n]);
    //x-=po[o[n]*2];
    x-=(long long)n*n%mod;
  }
  multiply(v1,v2,v);
  for(int h=0;h<v.size()&&h<=mod*2;h++)
  {
    x+=po[h]*v[h];
  }
  printf("%lld",x/2);
}