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;

typedef long long ll;
typedef long double ld;
using cd = complex<ld>;
const ld PI = acos(-1);

int inverse(int x, int lg_n) {
  int y = 0;
  for (int i = 0; i < lg_n; i++) {
    if (x & (1 << i)) {
      y ^= (1 << (lg_n - 1 - i));
    }
  }
  return y;
}

void fft(vector<cd> &a, bool inv) {
  int n = (int) a.size(), lg_n = log2(n);
  for (int i = 0; i < n; i++) {
    int j = inverse(i, lg_n);
    if (i < j) {
      swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len *= 2) {
    double ang = 2 * PI / len * (inv ? -1 : 1);
    cd mul(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      cd w(1);
      for (int j = 0; j < len / 2; j++) {
        cd x = a[i + j], y = a[i + len / 2 + j] * w;
        a[i + j] = x + y;
        a[i + len / 2 + j] = x - y;
        w *= mul;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; i++) {
      a[i] /= n;
    }
  }
}

vector<ll> multiply(vector<ll> &xa, vector<ll> &xb) {
  vector<cd> a(xa.begin(), xa.end()), b(xb.begin(), xb.end());
  int n = 1;
  while (n < (int) a.size() + (int) b.size()) {
    n *= 2;
  }
  a.resize(n);
  b.resize(n);
  fft(a, 0);
  fft(b, 0);
  for (int i = 0; i < n; i++) {
    a[i] *= b[i];
  }
  fft(a, 1);
  vector<ll> sol(n);
  for (int i = 0; i < n; i++) {
    sol[i] = round(real(a[i]));
  }
  return sol;
}


const int M = 200003;
int pt[M], goback[2 * M];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll sol = 0;
  int x = 1;
  for (int i = 0; i < M; i++) {
    pt[x] = i;
    goback[i] = x;
    goback[i + M - 1] = x;
    x = 2 * x % M;
  }
  vector<ll> a(M, 0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x == 0) {
      continue;
    }
    sol -= (ll) x * x % M;
    a[pt[x]]++;
  }
  a = multiply(a, a);
  for (int i = 0; i < 2 * M; i++) {
    if (a[i]) {
      int val = goback[i];
      sol += a[i] * val;
    }
  }
  sol /= 2;
  cout << sol << "\n";
  return 0;
}