#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <complex>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

typedef complex<double> Cp;

const int L = 19, N = 1 << L;
const double PI = 3.1415926535897932384626;

Cp a[N], b[N], w[N];
int brev[N];

void fft(Cp* a, int lgn, int sgn) {
  int n = 1 << lgn;
  if (sgn == 1) {
    for (int i = 1; i < n; ++i)
      brev[i] = brev[i >> 1] >> 1 | (i & 1) << (lgn - 1);

    for (int i = 0; i < n; ++i)
      w[i] = Cp(cos(2 * PI * i / n), sin(2 * PI * i / n));
  }

  for (int i = 0; i < n; ++i)
    if (brev[i] < i)
      swap(a[i], a[brev[i]]);

  for (int i = 0; i < lgn; ++i) {
    for (int j = 0; j < n; j += 2 << i) {
      Cp* ar = a + j;
      for (int k = 0; k < 1 << i; ++k) {
        Cp a0 = ar[k], a1 = ar[k + (1 << i)], x = a1 * w[k << (lgn - i - 1)];
        ar[k] = a0 + x;
        ar[k + (1 << i)] = a0 - x;
      }
    }
  }

  if (sgn == -1) {
    reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] /= n;
  }
}


const int P = 200003, R = 2;

int pw[P], ind[P], cnt[P];
ll ans;

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int q = 1;
  for (int i = 0; i < P - 1; ++i) {
    pw[i] = q;
    ind[q] = i;
    q = q * (ll)R % P;
  }

  int n;
  cin >> n;
  while (n--) {
    int x;
    cin >> x;
    if (!x)continue;
    ans -= x * (ll)x % P;
    ++cnt[ind[x]];
  }
  for (int i = 0; i < P - 1; ++i)
    a[i].real(cnt[i]);
  fft(a, 19, 1);
  for (int i = 0; i < 1 << 19; ++i)
    a[i] *= a[i];
  fft(a, 19, -1);
  q = 1;
  for (int i = 0; i < 1 << 19; ++i) {
    ll occ = a[i].real() + .5;
    ans += q * occ;
    q = q * (ll)R % P;
  }
  cout << ans / 2 << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <complex>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

typedef complex<double> Cp;

const int L = 19, N = 1 << L;
const double PI = 3.1415926535897932384626;

Cp a[N], b[N], w[N];
int brev[N];

void fft(Cp* a, int lgn, int sgn) {
  int n = 1 << lgn;
  if (sgn == 1) {
    for (int i = 1; i < n; ++i)
      brev[i] = brev[i >> 1] >> 1 | (i & 1) << (lgn - 1);

    for (int i = 0; i < n; ++i)
      w[i] = Cp(cos(2 * PI * i / n), sin(2 * PI * i / n));
  }

  for (int i = 0; i < n; ++i)
    if (brev[i] < i)
      swap(a[i], a[brev[i]]);

  for (int i = 0; i < lgn; ++i) {
    for (int j = 0; j < n; j += 2 << i) {
      Cp* ar = a + j;
      for (int k = 0; k < 1 << i; ++k) {
        Cp a0 = ar[k], a1 = ar[k + (1 << i)], x = a1 * w[k << (lgn - i - 1)];
        ar[k] = a0 + x;
        ar[k + (1 << i)] = a0 - x;
      }
    }
  }

  if (sgn == -1) {
    reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] /= n;
  }
}


const int P = 200003, R = 2;

int pw[P], ind[P], cnt[P];
ll ans;

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int q = 1;
  for (int i = 0; i < P - 1; ++i) {
    pw[i] = q;
    ind[q] = i;
    q = q * (ll)R % P;
  }

  int n;
  cin >> n;
  while (n--) {
    int x;
    cin >> x;
    if (!x)continue;
    ans -= x * (ll)x % P;
    ++cnt[ind[x]];
  }
  for (int i = 0; i < P - 1; ++i)
    a[i].real(cnt[i]);
  fft(a, 19, 1);
  for (int i = 0; i < 1 << 19; ++i)
    a[i] *= a[i];
  fft(a, 19, -1);
  q = 1;
  for (int i = 0; i < 1 << 19; ++i) {
    ll occ = a[i].real() + .5;
    ans += q * occ;
    q = q * (ll)R % P;
  }
  cout << ans / 2 << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

```