#include<bits/stdc++.h>
#define MOD 1000000007
#define Nmax 1000100
#define FOR(i, to) for (int i = 0; i < (to); ++i)
#define P 200003
using namespace std;
typedef long long ll;
const int MAX = 1<<20;

typedef ll value;
value a[MAX], b[MAX], cnt[P];
typedef complex<double> comp;
int N, p[MAX], ex[MAX], g[MAX];
comp omega[MAX], omega_tmp[MAX], a1[MAX], a2[MAX], z1[MAX], z2[MAX];

void fft(comp *a, comp *z) {
  FOR(i, N) z[i] = a[p[i]];
  int t = N;
  for (int size = 1; size < N; size *= 2) {
    t /= 2; FOR(j,size) omega_tmp[j] = omega[j*t];    
    for (int i = 0; i < N; i += 2*size) {
			FOR(j,size) {
			  comp c = omega_tmp[j] * z[i+j+size];
			  z[i+j+size] = z[i+j] - c; z[i+j] += c;
			}
    }
  }
}

void mult(value *a, value *b, value *c, int len) {
  N = 2*len; while (N & (N-1)) ++N;
  p[0] = 0; int k = 0, t = -1;
  while ((1 << k) < N) ++k;
  for(int i = 1; i < N; ++i) {
    if ((i&(i-1)) == 0) ++t;
    p[i] = p[i^(1<<t)]; p[i] |= 1 << (k-t-1);
  } 
  FOR (i, N) { a1[i] = 0; a2[i] = 0; }
  FOR (i, len) { a1[i] = double(a[i]); a2[i] = double(b[i]); }
  FOR (i, N/2) {
    omega[i] = polar(1.0, 2*M_PI/N*i);
    omega[N-i-1] = conj(omega[i]);
  }
  fft(a1, z1); fft(a2, z2);
  FOR (i, N) omega[i] = conj(omega[i]);
  FOR (i, N) a1[i] = z1[i] * z2[i] / comp(N, 0);
  fft(a1, z1);
  FOR (i, 2*len) c[i] = value(round(z1[i].real()));
}

int main() {
  int x = 1;
  ex[x] = 0;
  g[0] = x;
  a[0] = 0;
  for(int i=1;i<=P-2;++i) {
    x = (2LL*x) % P;
    ex[x] = i;
    g[i] = x;
    a[i] = 0;
  }
  
  int M;
  cin>>M;
  for(int i=0;i<M;++i) {
    cin>>x;
    if(!x) continue;
    ++a[ex[x]];
  }
  for(int i=0;i<=P-2;++i) {
    cnt[((2*i) % (P-1))] -= a[i]; 
  }
  
  mult(a, a, b, P-1);

  for(int i=0;i<2*P;++i) {
    cnt[i%(P-1)] += b[i];
  }
  ll ret = 0;
  for(int i=0;i<=P-2;++i) {
    ret += cnt[i] * g[i];
  }
  cout<<ret/2<<"\n";
  
  return 0;
}
### Prompt

Your task is to create a cpp solution to the following 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

### Response

```cpp
#include<bits/stdc++.h>
#define MOD 1000000007
#define Nmax 1000100
#define FOR(i, to) for (int i = 0; i < (to); ++i)
#define P 200003
using namespace std;
typedef long long ll;
const int MAX = 1<<20;

typedef ll value;
value a[MAX], b[MAX], cnt[P];
typedef complex<double> comp;
int N, p[MAX], ex[MAX], g[MAX];
comp omega[MAX], omega_tmp[MAX], a1[MAX], a2[MAX], z1[MAX], z2[MAX];

void fft(comp *a, comp *z) {
  FOR(i, N) z[i] = a[p[i]];
  int t = N;
  for (int size = 1; size < N; size *= 2) {
    t /= 2; FOR(j,size) omega_tmp[j] = omega[j*t];    
    for (int i = 0; i < N; i += 2*size) {
			FOR(j,size) {
			  comp c = omega_tmp[j] * z[i+j+size];
			  z[i+j+size] = z[i+j] - c; z[i+j] += c;
			}
    }
  }
}

void mult(value *a, value *b, value *c, int len) {
  N = 2*len; while (N & (N-1)) ++N;
  p[0] = 0; int k = 0, t = -1;
  while ((1 << k) < N) ++k;
  for(int i = 1; i < N; ++i) {
    if ((i&(i-1)) == 0) ++t;
    p[i] = p[i^(1<<t)]; p[i] |= 1 << (k-t-1);
  } 
  FOR (i, N) { a1[i] = 0; a2[i] = 0; }
  FOR (i, len) { a1[i] = double(a[i]); a2[i] = double(b[i]); }
  FOR (i, N/2) {
    omega[i] = polar(1.0, 2*M_PI/N*i);
    omega[N-i-1] = conj(omega[i]);
  }
  fft(a1, z1); fft(a2, z2);
  FOR (i, N) omega[i] = conj(omega[i]);
  FOR (i, N) a1[i] = z1[i] * z2[i] / comp(N, 0);
  fft(a1, z1);
  FOR (i, 2*len) c[i] = value(round(z1[i].real()));
}

int main() {
  int x = 1;
  ex[x] = 0;
  g[0] = x;
  a[0] = 0;
  for(int i=1;i<=P-2;++i) {
    x = (2LL*x) % P;
    ex[x] = i;
    g[i] = x;
    a[i] = 0;
  }
  
  int M;
  cin>>M;
  for(int i=0;i<M;++i) {
    cin>>x;
    if(!x) continue;
    ++a[ex[x]];
  }
  for(int i=0;i<=P-2;++i) {
    cnt[((2*i) % (P-1))] -= a[i]; 
  }
  
  mult(a, a, b, P-1);

  for(int i=0;i<2*P;++i) {
    cnt[i%(P-1)] += b[i];
  }
  ll ret = 0;
  for(int i=0;i<=P-2;++i) {
    ret += cnt[i] * g[i];
  }
  cout<<ret/2<<"\n";
  
  return 0;
}
```