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;

const int MAX_N = 1 << 20, BLKSIZ = 50;
const int P2 = 200003, P2R = 2;
const ll P = 998244353, PR = 3;

ll sq(ll x) { return x * x % P; }
ll qpow(ll a, ll b) { return b ? sq(qpow(a, b / 2)) * (b & 1 ? a : 1) % P : 1; }
ll inv(ll x) { return qpow(x, P - 2); }

ll omega[MAX_N], disc_log[P2], disc_pow[P2];

void NTT(ll A[], int n, int d = 1) {
    for (int i = 0, j = 0; i < n; i++) {
        if (i < j) swap(A[i], A[j]);
        for (int k = n / 2; (j ^= k) < k; k /= 2);
    }
    for (int i = 1; i < n; i *= 2) {
        ll u = omega[(MAX_N + d * MAX_N / (2 * i)) % MAX_N];
        for (int j = 0; j < n; j += 2 * i) {
            ll v = 1;
            for (int k = 0; k < i; k++) {
                ll a = A[j + k], b = A[j + k + i] * v % P;
                A[j + k] = (a + b) % P; A[j + k + i] = (a - b + P) % P;
                (v *= u) %= P;
            }
        }
    }
    if (d == -1) {
        ll inv_n = inv(n);
        for (int i = 0; i < n; i++) (A[i] *= inv_n) %= P;
    }
}

void init() {
    omega[0] = 1; omega[1] = qpow(PR, (P - 1) / MAX_N);
    for (int i = 2; i < MAX_N; i++) omega[i] = omega[i - 1] * omega[1] % P;
    disc_pow[0] = 1;
    for (int i = 1; i < P2; i++) disc_pow[i] = disc_pow[i - 1] * P2R % P2;
    for (int i = 0; i < P2 - 1; i++) disc_log[disc_pow[i]] = i;
}

void solve() {
    static ll A[MAX_N];
    ll ans = 0;
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        ll a; scanf("%lld", &a);
        if (a) {
            ans -= a * a % P2;
            A[disc_log[a]]++;
        }
    }
    for (int i = 0; i < P2 - 1; i++) {
        if (A[i] > BLKSIZ) {
            for (int j = 0; j < P2 - 1; j++) {
                ans += A[i] * A[j] * (i == j ? 1 : 2) * disc_pow[(i + j) % (P2 - 1)];
            }
            A[i] = 0;
        }
    }
    NTT(A, MAX_N);
    for (int i = 0; i < MAX_N; i++)
        A[i] = sq(A[i]);
    NTT(A, MAX_N, -1);
    for (int i = 0; i < MAX_N; i++) {
        ans += A[i] * disc_pow[i % (P2 - 1)];
    }
    ans /= 2;
    printf("%lld\n", ans);
}

int main() {
    init();
    solve();
}