#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define complex hhcom
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 200003;
const int gg = 2;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const double pi = acos(-1);
struct complex {
  double x, y;
  inline complex operator + (const complex &b) const {
    return (complex){x + b.x, y + b.y};
  }
  inline complex operator - (const complex &b) const {
    return (complex){x - b.x, y - b.y};
  }
  inline complex operator * (const complex &b) const {
    return (complex) {
      x * b.x - y * b.y,
      y * b.x + x * b.y
    };
  }
};
const int N = 10e5 + 5;
complex f[N];

int to[N], oto[N], rev[N];
int n;
//
inline void getrev(int len) {
  rep(i, len) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len / 2);
}
void fft(complex *f, int len, int dft) {
  rep(i, len) if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int step = 1; step < len; step <<= 1) {
    complex wn = (complex){cos(pi / step), sin(dft * pi / step)};
    for (int i = 0; i < len; i += step << 1) {
      complex wnk = (complex){1, 0};
      for (int j = i; j < i + step; j++) {
        complex x = f[j], y = f[j + step] * wnk;
        f[j] = x + y; f[j + step] = x - y;
        wnk = wnk * wn;
      }
    }
  }
  if (dft == -1) rep(i, len) f[i].x /= len;
}
int main() {
  n = getint();
  for (int i = 0, j = 1; i < mod - 1; i++, j = mul(j, gg)) {
    to[j] = i; oto[i] = j;
  }
  ll res = 0;
  rep(i, n) {
    int x = getint();
    if (x) {
      res -= mul(x, x);
      ++f[to[x]].x;
    }
  }
  int len = 1;
  while (len < mod + mod - 3) len <<= 1;
  getrev(len);
  fft(f, len, 1);
  rep(i, len) f[i] = f[i] * f[i];
  fft(f, len, -1);
  rep(i, len) {
    res += 1ll * oto[i % (mod - 1)] * (ll)(f[i].x + 0.5);
  }
  cout << res / 2 << endl;
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define complex hhcom
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 200003;
const int gg = 2;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const double pi = acos(-1);
struct complex {
  double x, y;
  inline complex operator + (const complex &b) const {
    return (complex){x + b.x, y + b.y};
  }
  inline complex operator - (const complex &b) const {
    return (complex){x - b.x, y - b.y};
  }
  inline complex operator * (const complex &b) const {
    return (complex) {
      x * b.x - y * b.y,
      y * b.x + x * b.y
    };
  }
};
const int N = 10e5 + 5;
complex f[N];

int to[N], oto[N], rev[N];
int n;
//
inline void getrev(int len) {
  rep(i, len) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len / 2);
}
void fft(complex *f, int len, int dft) {
  rep(i, len) if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int step = 1; step < len; step <<= 1) {
    complex wn = (complex){cos(pi / step), sin(dft * pi / step)};
    for (int i = 0; i < len; i += step << 1) {
      complex wnk = (complex){1, 0};
      for (int j = i; j < i + step; j++) {
        complex x = f[j], y = f[j + step] * wnk;
        f[j] = x + y; f[j + step] = x - y;
        wnk = wnk * wn;
      }
    }
  }
  if (dft == -1) rep(i, len) f[i].x /= len;
}
int main() {
  n = getint();
  for (int i = 0, j = 1; i < mod - 1; i++, j = mul(j, gg)) {
    to[j] = i; oto[i] = j;
  }
  ll res = 0;
  rep(i, n) {
    int x = getint();
    if (x) {
      res -= mul(x, x);
      ++f[to[x]].x;
    }
  }
  int len = 1;
  while (len < mod + mod - 3) len <<= 1;
  getrev(len);
  fft(f, len, 1);
  rep(i, len) f[i] = f[i] * f[i];
  fft(f, len, -1);
  rep(i, len) {
    res += 1ll * oto[i % (mod - 1)] * (ll)(f[i].x + 0.5);
  }
  cout << res / 2 << endl;
  return 0;
}

```