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 pair<int,int> pii;
#define fir first
#define sec second
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

typedef double db;
const db pi = acos(-1);
const int N = 800010;
int rev[N];
void prework(int n) {
  rev[0] = 0;
  rep (i, 1, n-1)
    if (i&1) rev[i] = rev[i^1] | (n >> 1);
    else rev[i] = rev[i >> 1] >> 1;
}
struct cpl {
  db x,y;
  cpl(db x=0,db y=0): x(x), y(y) {}
  cpl operator + (const cpl& a) const {
    return cpl(x + a.x, y + a.y);
  }
  cpl operator - (const cpl& a) const {
    return cpl(x - a.x, y - a.y);
  }
  cpl operator * (const cpl& a) const {
    return cpl(x * a.x - y * a.y, x * a.y + y * a.x);
  }
  cpl operator / (const db& a) const {
    return cpl(x / a, y / a);
  }
};
void dft(cpl* a,int n,int sgn) {
  rep (i, 0, n-1) if (rev[i] < i)
    swap(a[i], a[rev[i]]);
  cpl w, wp, u, v;
  for (int s = 2; s <= n; s <<= 1) {
    wp = cpl(cos(2 * pi / s), sin(2 * pi / s));
    if (sgn) wp.y = -wp.y;
    for (int k = 0; k < n; k += s) {
      w = cpl(1, 0);
      for (int j = 0; j < (s >> 1); ++ j) {
        u = a[k + j];
        v = a[k + j + (s >> 1)] * w;
        a[k + j] = u + v;
        a[k + j + (s >> 1)] = u - v;
        w = w * wp;
      }
    }
  }
  if (sgn) {
    rep (i, 0, n-1) a[i] = a[i] / n;
  }
}

const int MOD = 200003, G = 5;
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = (ll)ret * a % MOD;
    a = (ll)a * a % MOD;
    b >>= 1;
  }
  return ret;
}
int n, val[N], key[MOD + 10], num[N];
ll tnum[N];
cpl ta[N];
ll ans;
int main() {
  read(n);
  rep (i, 1, n) read(val[i]);
  for (int i = 0, j = 1; i < MOD - 1; ++ i, j = (ll)j * G % MOD)
    key[j] = i;
  rep (i, 1, n) if (val[i] != 0) {
    ++ num[key[val[i]]];
    // cerr << key[val[i]] << endl;
  }
  int l = 1;
  while (l < 2 * MOD) l <<= 1;
  prework(l);
  rep (i, 0, MOD - 2) ta[i] = cpl(num[i], 0);
  dft(ta, l, 0);
  rep (i, 0, l-1) ta[i] = ta[i] * ta[i];
  dft(ta, l, 1);
  rep (i, 0, l-1) tnum[i] = (ll)(ta[i].x + 0.5);
  rep (i, 0, 2 * MOD) if (tnum[i]) {
    ans += power(G, i) * tnum[i];
    // cerr << i << ' ' << tnum[i] << endl;
  }
  rep (i, 1, n) ans -= (ll)val[i] * val[i] % MOD;
  ans /= 2;
  cout << ans << endl;
  return 0;
}