#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

LL mpow(LL a, LL i, LL M) {
    if (i == 0) return 1;
    LL r = mpow(a * a % M, i >> 1, M);
    if (i & 1) r = r * a % M;
    return r;
}

// NTT WEST
void NTT(vector<LL>& A, LL M, LL g) {
    int N = A.size();
    for (int i = 0, j = 0; j < N; j++) {
        if (i < j) swap(A[i], A[j]);
        for (int k = N >> 1; k > (i ^= k); k >>= 1);
    }
    for (int i = 1; i < N; i <<= 1) {
        LL q = mpow(g, (M - 1) / i / 2, M);
        LL qj = 1;
        rep(j, i){
            for (int k = j; k < N; k += i * 2) {
                LL l = A[k], r = A[k + i] * qj % M;
                A[k] = (l + r) % M;
                A[k + i] = (l + M - r) % M;
            }
            qj = qj * q % M;
        }
    }
}

struct Fuse { LL M, G; };

// trinitrotoluene EXPLODING!!
vector<LL> TNT(const vector<LL>& A, const vector<LL>& B, Fuse F) {
    int Z = 1; while (Z < A.size() + B.size()) Z <<= 1;
    vector<LL> ans(Z), Ax(Z), Bx(Z);
    LL iZ = mpow(Z, F.M - 2, F.M);
    rep(i, Z) Ax[i] = Bx[i] = 0;
    rep(i, A.size()) Ax[i] = A[i];
    rep(i, B.size()) Bx[i] = B[i];
    NTT(Ax, F.M, F.G);
    NTT(Bx, F.M, F.G);
    rep(i, Z) ans[i] = Ax[i] * Bx[i] % F.M;
    NTT(ans, F.M, mpow(F.G, F.M - 2, F.M));
    rep(i, Z) ans[i] = ans[i] * iZ % F.M;
    return move(ans);
}

const Fuse fuse[2] = { {998244353,3}, {1107296257,10} };

LL ExtGcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    LL g = ExtGcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

struct ModEq {
    LL c1, c2, t1, t2, M;
    ModEq(LL m1, LL m2) {
        ExtGcd(m1, m2, c1, c2);
        c1 = (c1 + m2) % m2;
        c2 = (c2 + m1) % m1;
        t1 = m1; t2 = m2;
        M = m1 * m2;
    }
    LL operator()(LL a1, LL a2) {
        LL d = a1 + (a2 - a1) * c1 % t2 * t1;
        return (d + M) % M;
    }
};

const LL M = 200003;
int N;
LL I[M];
vector<LL> A;
vector<LL> C[2];

int main() {
    scanf("%d", &N);
    for (int i = 0, j = 1; i < M - 1; i++, j = j * 2 % M) I[j] = i;
    A.resize(M - 1);
    rep(i, N) {
        int a; scanf("%d", &a);
        if (a) A[I[a]]++;
    }
    rep(i, 2) C[i] = TNT(A, A, fuse[i]);
    ModEq X(fuse[0].M, fuse[1].M);
    rep(i, C[0].size()) C[0][i] = X(C[0][i], C[1][i]);
    rep(i, M - 1) C[0][i * 2] -= A[i];
    for (LL& c : C[0]) c /= 2;

    LL ans = 0;
    for (int i = 0, j = 1; i < C[0].size(); i++, j = j * 2 % M)
        ans += C[0][i] * j;

    cout << ans << endl;

    return 0;
}

### Prompt

In Cpp, your task is to solve 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;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

LL mpow(LL a, LL i, LL M) {
    if (i == 0) return 1;
    LL r = mpow(a * a % M, i >> 1, M);
    if (i & 1) r = r * a % M;
    return r;
}

// NTT WEST
void NTT(vector<LL>& A, LL M, LL g) {
    int N = A.size();
    for (int i = 0, j = 0; j < N; j++) {
        if (i < j) swap(A[i], A[j]);
        for (int k = N >> 1; k > (i ^= k); k >>= 1);
    }
    for (int i = 1; i < N; i <<= 1) {
        LL q = mpow(g, (M - 1) / i / 2, M);
        LL qj = 1;
        rep(j, i){
            for (int k = j; k < N; k += i * 2) {
                LL l = A[k], r = A[k + i] * qj % M;
                A[k] = (l + r) % M;
                A[k + i] = (l + M - r) % M;
            }
            qj = qj * q % M;
        }
    }
}

struct Fuse { LL M, G; };

// trinitrotoluene EXPLODING!!
vector<LL> TNT(const vector<LL>& A, const vector<LL>& B, Fuse F) {
    int Z = 1; while (Z < A.size() + B.size()) Z <<= 1;
    vector<LL> ans(Z), Ax(Z), Bx(Z);
    LL iZ = mpow(Z, F.M - 2, F.M);
    rep(i, Z) Ax[i] = Bx[i] = 0;
    rep(i, A.size()) Ax[i] = A[i];
    rep(i, B.size()) Bx[i] = B[i];
    NTT(Ax, F.M, F.G);
    NTT(Bx, F.M, F.G);
    rep(i, Z) ans[i] = Ax[i] * Bx[i] % F.M;
    NTT(ans, F.M, mpow(F.G, F.M - 2, F.M));
    rep(i, Z) ans[i] = ans[i] * iZ % F.M;
    return move(ans);
}

const Fuse fuse[2] = { {998244353,3}, {1107296257,10} };

LL ExtGcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    LL g = ExtGcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

struct ModEq {
    LL c1, c2, t1, t2, M;
    ModEq(LL m1, LL m2) {
        ExtGcd(m1, m2, c1, c2);
        c1 = (c1 + m2) % m2;
        c2 = (c2 + m1) % m1;
        t1 = m1; t2 = m2;
        M = m1 * m2;
    }
    LL operator()(LL a1, LL a2) {
        LL d = a1 + (a2 - a1) * c1 % t2 * t1;
        return (d + M) % M;
    }
};

const LL M = 200003;
int N;
LL I[M];
vector<LL> A;
vector<LL> C[2];

int main() {
    scanf("%d", &N);
    for (int i = 0, j = 1; i < M - 1; i++, j = j * 2 % M) I[j] = i;
    A.resize(M - 1);
    rep(i, N) {
        int a; scanf("%d", &a);
        if (a) A[I[a]]++;
    }
    rep(i, 2) C[i] = TNT(A, A, fuse[i]);
    ModEq X(fuse[0].M, fuse[1].M);
    rep(i, C[0].size()) C[0][i] = X(C[0][i], C[1][i]);
    rep(i, M - 1) C[0][i * 2] -= A[i];
    for (LL& c : C[0]) c /= 2;

    LL ans = 0;
    for (int i = 0, j = 1; i < C[0].size(); i++, j = j * 2 % M)
        ans += C[0][i] * j;

    cout << ans << endl;

    return 0;
}

```