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;

namespace FFT {

typedef double dbl;
typedef complex<dbl> cplx;
const dbl pi = acos(-1);

const int W = 19, S = 1 << W;

int m, s;
int r[S];
void init(int n) {
    for (s = 0, m = 1; m < n; m <<= 1, ++s);
    for (int i = 0; i != m; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (s - 1));
}

void fft(cplx* p, const int t) {
    for (int i = 0; i != m; ++i) if (i < r[i]) swap(p[i], p[r[i]]);
    for (int i = 1; i != m; i <<= 1) {
        cplx w0{ cos(pi / i), (t ? -1 : 1) * sin(pi / i) };
        for (int j = 0; j != m; j += (i << 1)) {
            cplx w{ 1, 0 };
            for (int k = 0; k != i; k++) {
                cplx u = p[j + k], v = w * p[i + j + k];
                p[j + k] = u + v; p[i + j + k] = u - v;
                w *= w0;
            }
        }
    }
}

void fft2(cplx* p, cplx* q, const int t) {
    for (int i = 0; i < m; ++i) p[i].imag(q[i].real());
    fft(p, t);
    for (int i = 0; i < m; ++i) q[i] = conj(p[i ? m - i : 0]);
    for (int i = 0; i < m; ++i) {
        cplx u = (p[i] + q[i]) / 2., v = (p[i] - q[i]) / 2.;
        p[i] = u; q[i] = cplx(0, -1) * v;
    }
}

cplx px[S], py[S], pz[S];
vector<ll> conv(const vector<int>& a, const vector<int>& b) {
    int n1 = a.size(), n2 = b.size(), n3 = n1 + n2 - 1; init(n3);
    for (int i = 0; i < m; ++i) px[i] = cplx(i < n1 ? a[i] : 0, 0);
    for (int i = 0; i < m; ++i) py[i] = cplx(i < n2 ? b[i] : 0, 0);
    fft2(px, py, 0);
    for (int i = 0; i < m; ++i) pz[i] = px[i] * py[i];
    fft(pz, 1);
    vector<ll> c(n3);
    for (int i = 0; i < n3; ++i) c[i] = round(pz[i].real() / m);
    return c;
}

}

using FFT::conv;

const int P = 200003;
int l[P], w[P];

int main(void) {
    for (int i = 0, q = 1; i < P - 1; ++i, q = (q + q) % P) l[q] = i, w[i] = q;
    vector<int> c(P - 1, 0);
    int n; scanf("%d", &n);
    vector<int> a(n);
    for (int& i : a) {
        scanf("%d", &i);
        if (i) c[l[i]]++;
    }
    vector<ll> d = conv(c, c);
    
    ll sum = 0;
    for (int i = 0; i < d.size(); ++i)
        sum += d[i] * w[i % (P - 1)];
    
    for (int i = 0; i < a.size(); ++i)
        sum -= 1ll * a[i] * a[i] % P;
    printf("%lld\n", sum / 2);    
    return 0;
}