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;
typedef complex<double> cd;

const int LOG = 20;
const int N = 1 << LOG;
const ld PI = acos(-1);

cd w[N];

void init() {
    for (int i = 0; i < N; i++) {
        w[i] = cd(cos(i * 2 * PI / N), sin(i * 2 * PI / N));
    }
}

static void fft(vector<cd> &A, int _LOG) {
    int _N = 1 << _LOG;
    vector<int> rev(_N);
    for (int i = 1; i < _N; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (_LOG - 1));
        if (i < rev[i]) {
            swap(A[i], A[rev[i]]);
        }
    }
    for (int lvl = 0; lvl < _LOG; lvl++) {
        int len = (1 << lvl);
        for (int i = 0; i < _N; i += 2 * len) {
            for (int j = 0; j < len; j++) {
                cd x = A[i + j], y = A[i + len + j] * w[j << (LOG - 1 - lvl)];
                A[i + j] = x + y;
                A[i + len + j] = x - y;
            }
        }
    }
}

vector<ll> operator*(vector<ll> a, vector<ll> b) {
    int n = max(a.size(), b.size());
    int _N = 1, _LOG = 0;
    while (_N <= 2 * n) {
        _N *= 2;
        _LOG++;
    }
    vector<cd> A(a.begin(), a.end()), B(b.begin(), b.end());
    A.resize(_N);
    B.resize(_N);
    fft(A, _LOG);
    fft(B, _LOG);
    for (int i = 0; i < _N; i++) {
        A[i] *= B[i];
    }
    fft(A, _LOG);
    reverse(A.begin() + 1, A.end());
    vector<ll> c(_N);
    ll carry = 0;
    for (int i = 0; i < _N; i++) {
        c[i] = round(A[i].real() / _N) + carry;
    }
    return c;
}

int main() {
    cout.precision(20); cout << fixed;
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    init();
    int mod = 200003;
    int g = 2;
    vector<int> root(mod);
    vector<int> pw(1e6);
    int y = 1;
    for (int i = 0; i < mod; i++) {
        root[y] = i;
        y = (y * g) % mod;
    }
    y = 1;
    for (int i = 0; i < 1e6; i++) {
        pw[i] = y;
        y = (y * g) % mod;
    }
    int n;
    cin >> n;
    vector<ll> a(mod), v;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x != 0) {
            v.push_back(x);
            a[root[x]]++;
        }
    }
    n = v.size();
    a = a * a;
    for (int i = 0; i < n; i++) {
        a[root[v[i]] * 2]--;
    }
    ll ans = 0;
    for (int i = 0; i < a.size(); i++) {
        ans += (a[i] / 2) * pw[i];
    }
    cout << ans;
}