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;

const int N = 1 << 20;

namespace POLY {
    const int mo = 998244353;
    const double PI = acos(-1.0);
    int fpm(int x, int y) {
        int ans = 1;
        for (; y > 0; y >>= 1) {
            if (y & 1)
                ans = 1ll * ans * x % mo;
            x = 1ll * x * x % mo;
        }
        return ans;
    }

    int n;
    void init(int _n) {
       n = _n;
       while(n > (n & -n)) n += (n & -n);
    }

    void dft(complex<double> *x, int t) {
        for(int i = 0, j = 0; i < n; ++i) {
            if(i < j) swap(x[i], x[j]);
            for(int l = n >> 1; (j ^= l) < l; l >>= 1);
        }

        for(int l = 1; l < n; l <<= 1) {
            complex <double> wn(cos(t * PI / l), sin(t * PI / l));

            for(int i = 0; i < n; i += (l << 1)) {
                complex <double> w(1, 0);

                for(int j = 0; j < l; ++j) {
                    complex <double> a = x[i + j];
                    complex <double> b = x[i + j + l] * w;

                    w = w * wn;
                    x[i + j] = a + b;
                    x[i + j + l] = a - b;
                }
            }
        }

        if(!~t) {
            for(int i = 0; i < n; ++i) { x[i] = x[i] / (double) n; }
        }
    }
}

const int mo = 2e5 + 3;

int n;
int a[N + 5], _exp[mo + 5], _log[mo + 5];
complex<double> x[N + 5];

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
#endif

    int t = 1;
    for (int i = 0; i < mo-1; ++i) {
        _log[_exp[i] = t] = i;
        t = 2 * t % mo;
    }

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);

        if (a[i]) x[_log[a[i]]] += 1;
    }

    POLY::init(2 * mo);
    POLY::dft(x, +1);

    for (int i = 0; i < POLY::n; ++i) x[i] = x[i] * x[i];

    POLY::dft(x, -1);

    long long ans = 0;
    for (int i = 1; i <= n; ++i) if (a[i]) x[2 * _log[a[i]]] -= 1;
    for (int i = 0; i < 2 * mo; ++i) {
        ans += 1ll * _exp[i % (mo-1)] * ((long long) std::round(x[i].real()));
    }
    ans/=2;
    printf("%lld\n", ans);

    return 0;
}