#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct cplx {
  ld a, b;

  cplx (ld a = 0, ld b = 0) : a(a), b(b) {}
  
  const cplx operator + (const cplx &c) const {
    return cplx(a + c.a, b + c.b);
  }

  const cplx operator - (const cplx &c) const {
    return cplx(a - c.a, b - c.b);
  }

  const cplx operator * (const cplx &c) const {
    return cplx(a * c.a - b * c.b, a * c.b + b * c.a);
  }

  const cplx conj() const {
    return cplx(a, -b);
  }
};

const ld PI = acosl(-1);
const int N = (1 << 20) + 5;

int rev[N]; cplx w[N];

void prepare (int &n) { 
  int sz = __builtin_ctz(n);
  for (int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
  w[0] = 0, w[1] = 1, sz = 1; 
  while (1 << sz < n) {
    ld ang = 2 * PI / (1 << (sz + 1));
    cplx w_n = cplx(cosl(ang), sinl(ang));
    for (int i = 1 << (sz - 1); i < (1 << sz); ++i) {
      w[i << 1] = w[i], w[i << 1 | 1] = w[i] * w_n; 
    } ++sz;
  }
}

void fft (cplx *a, int n) { 
  for (int i = 1; i < n - 1; ++i) { 
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  }
  for (int h = 1; h < n; h <<= 1) {
    for (int s = 0; s < n; s += h << 1) {
      for (int i = 0; i < h; ++i) {
        cplx &u = a[s + i], &v = a[s + i + h], t = v * w[h + i];
        v = u - t, u = u + t;
      }
    }
  }
}

static cplx f[N], g[N], u[N], v[N];

void multiply (ll *a, ll *b, int n, int m) {
  int sz = n + m - 1; 
  while (sz & (sz - 1)) sz = (sz | (sz - 1)) + 1;
  prepare(sz);
  for (int i = 0; i < sz; ++i) f[i] = cplx(i < n ? a[i] : 0, i < m ? b[i] : 0);
  fft(f, sz);
  for (int i = 0; i <= (sz >> 1); ++i) {
    int j = (sz - i) & (sz - 1); 
    cplx x = (f[i] * f[i] - (f[j] * f[j]).conj()) * cplx(0, -0.25); 
    f[j] = x, f[i] = x.conj(); 
  }
  fft(f, sz); 
  for(int i = 0; i < sz; ++i) a[i] = f[i].a / sz + 0.5; 
}

const int MOD = 200003;

bitset <N> vis;
int n; ll a[N], inv[N];

int main() {
  ll cur = 1;
  for (int i = 0; i < MOD - 1; ++i) {
    inv[cur] = i;
    cur = cur * 2 % MOD;
  }
  cin >> n;
  ll ans = 0;
  while (n--) {
    int x;
    scanf("%d", &x);
    if (x) ++a[inv[x]];
    ans -= ((ll) x * x % MOD);
  }
  multiply(a, a, MOD, MOD);
  cur = 1;
  for (int i = 0; i < MOD + MOD; ++i) {
    ans += a[i] * cur;
    cur = cur * 2 % MOD;
  }
  ans >>= 1;
  cout << ans << '\n';
  return 0;
}


### Prompt

Create a solution in CPP for 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>

using namespace std;

typedef long long ll;
typedef long double ld;

struct cplx {
  ld a, b;

  cplx (ld a = 0, ld b = 0) : a(a), b(b) {}
  
  const cplx operator + (const cplx &c) const {
    return cplx(a + c.a, b + c.b);
  }

  const cplx operator - (const cplx &c) const {
    return cplx(a - c.a, b - c.b);
  }

  const cplx operator * (const cplx &c) const {
    return cplx(a * c.a - b * c.b, a * c.b + b * c.a);
  }

  const cplx conj() const {
    return cplx(a, -b);
  }
};

const ld PI = acosl(-1);
const int N = (1 << 20) + 5;

int rev[N]; cplx w[N];

void prepare (int &n) { 
  int sz = __builtin_ctz(n);
  for (int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
  w[0] = 0, w[1] = 1, sz = 1; 
  while (1 << sz < n) {
    ld ang = 2 * PI / (1 << (sz + 1));
    cplx w_n = cplx(cosl(ang), sinl(ang));
    for (int i = 1 << (sz - 1); i < (1 << sz); ++i) {
      w[i << 1] = w[i], w[i << 1 | 1] = w[i] * w_n; 
    } ++sz;
  }
}

void fft (cplx *a, int n) { 
  for (int i = 1; i < n - 1; ++i) { 
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  }
  for (int h = 1; h < n; h <<= 1) {
    for (int s = 0; s < n; s += h << 1) {
      for (int i = 0; i < h; ++i) {
        cplx &u = a[s + i], &v = a[s + i + h], t = v * w[h + i];
        v = u - t, u = u + t;
      }
    }
  }
}

static cplx f[N], g[N], u[N], v[N];

void multiply (ll *a, ll *b, int n, int m) {
  int sz = n + m - 1; 
  while (sz & (sz - 1)) sz = (sz | (sz - 1)) + 1;
  prepare(sz);
  for (int i = 0; i < sz; ++i) f[i] = cplx(i < n ? a[i] : 0, i < m ? b[i] : 0);
  fft(f, sz);
  for (int i = 0; i <= (sz >> 1); ++i) {
    int j = (sz - i) & (sz - 1); 
    cplx x = (f[i] * f[i] - (f[j] * f[j]).conj()) * cplx(0, -0.25); 
    f[j] = x, f[i] = x.conj(); 
  }
  fft(f, sz); 
  for(int i = 0; i < sz; ++i) a[i] = f[i].a / sz + 0.5; 
}

const int MOD = 200003;

bitset <N> vis;
int n; ll a[N], inv[N];

int main() {
  ll cur = 1;
  for (int i = 0; i < MOD - 1; ++i) {
    inv[cur] = i;
    cur = cur * 2 % MOD;
  }
  cin >> n;
  ll ans = 0;
  while (n--) {
    int x;
    scanf("%d", &x);
    if (x) ++a[inv[x]];
    ans -= ((ll) x * x % MOD);
  }
  multiply(a, a, MOD, MOD);
  cur = 1;
  for (int i = 0; i < MOD + MOD; ++i) {
    ans += a[i] * cur;
    cur = cur * 2 % MOD;
  }
  ans >>= 1;
  cout << ans << '\n';
  return 0;
}


```