#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Maxn 800005

using namespace std;

const LL P = 200003; const double PI = acos(-1.0);

inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while('0' <= c && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

LL n, m = 1, val[Maxn], mapp[Maxn], trans[Maxn], g[Maxn];

struct Point {
    double x, y;
}
f[Maxn];

Point Plus(Point a, Point b) {
    Point c;
    c.x = a.x + b.x; c.y = a.y + b.y;
    return c;
}

Point Minus(Point a, Point b) {
    Point c;
    c.x = a.x - b.x; c.y = a.y - b.y;
    return c;
}

Point Mul(Point a, Point b) {
    Point c;
    c.x = a.x * b.x - a.y * b.y;
    c.y = a.x * b.y + b.x * a.y;
    return c;
}

void DFT(Point *F, bool op) {
    for(int i = 0; i < m; ++i) trans[i] = (trans[i >> 1] >> 1) | ((i & 1) ? m >> 1 : 0);
    for(int i = 0; i < m; ++i) if(i < trans[i]) swap(F[i], F[trans[i]]);
    for(int len = 2; len <= m; len <<= 1) {
        Point base = {cos(2 * PI / len), sin(2 * PI / len)};
        if(op) base.y *= -1.0;
        for(int i = 0; i < m; i += len) {
            Point now = {1.0, 0.0};
            for(int k = i; k < i + (len >> 1); ++k) {
                Point temp = Mul(now, F[k + (len >> 1)]);
                F[k + (len >> 1)] = Minus(F[k], temp);
                F[k] = Plus(F[k], temp);
                now = Mul(now, base);
            }
        }
    }
}

int main() {
    n = read();
    for(int i = 1; i <= n; ++i) val[i] = read();
    LL mul = 1;
    for(int i = 0; i <= P - 2; ++i) {
        mapp[mul] = i;
        mul = mul * 2 % P;
    }
    for(int i = 1; i <= n; ++i)
        if(val[i]) ++f[mapp[val[i]]].x;
    while(m < 2 * P - 3) m <<= 1;
    // cout << m << endl;
    DFT(f, 0);
    for(int i = 0; i < m; ++i) f[i] = Mul(f[i], f[i]);
    DFT(f, 1);
    for(int i = 0; i < m; ++i) g[i] = f[i].x * 1.0 / m + 0.5;
    LL ans = 0; mul = 1;
    for(int i = 1; i <= n; ++i) {
        if(val[i]) --g[mapp[val[i]] * 2];
    }
    for(int i = 0; i <= P - 2; ++i) {
        ans += mul * (g[i] + g[i + P - 1]) / 2;
        mul = mul * 2 % P;
    }
    cout << ans << endl;
    return 0;
}
### Prompt

Create a solution in Cpp for 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 <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Maxn 800005

using namespace std;

const LL P = 200003; const double PI = acos(-1.0);

inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while('0' <= c && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

LL n, m = 1, val[Maxn], mapp[Maxn], trans[Maxn], g[Maxn];

struct Point {
    double x, y;
}
f[Maxn];

Point Plus(Point a, Point b) {
    Point c;
    c.x = a.x + b.x; c.y = a.y + b.y;
    return c;
}

Point Minus(Point a, Point b) {
    Point c;
    c.x = a.x - b.x; c.y = a.y - b.y;
    return c;
}

Point Mul(Point a, Point b) {
    Point c;
    c.x = a.x * b.x - a.y * b.y;
    c.y = a.x * b.y + b.x * a.y;
    return c;
}

void DFT(Point *F, bool op) {
    for(int i = 0; i < m; ++i) trans[i] = (trans[i >> 1] >> 1) | ((i & 1) ? m >> 1 : 0);
    for(int i = 0; i < m; ++i) if(i < trans[i]) swap(F[i], F[trans[i]]);
    for(int len = 2; len <= m; len <<= 1) {
        Point base = {cos(2 * PI / len), sin(2 * PI / len)};
        if(op) base.y *= -1.0;
        for(int i = 0; i < m; i += len) {
            Point now = {1.0, 0.0};
            for(int k = i; k < i + (len >> 1); ++k) {
                Point temp = Mul(now, F[k + (len >> 1)]);
                F[k + (len >> 1)] = Minus(F[k], temp);
                F[k] = Plus(F[k], temp);
                now = Mul(now, base);
            }
        }
    }
}

int main() {
    n = read();
    for(int i = 1; i <= n; ++i) val[i] = read();
    LL mul = 1;
    for(int i = 0; i <= P - 2; ++i) {
        mapp[mul] = i;
        mul = mul * 2 % P;
    }
    for(int i = 1; i <= n; ++i)
        if(val[i]) ++f[mapp[val[i]]].x;
    while(m < 2 * P - 3) m <<= 1;
    // cout << m << endl;
    DFT(f, 0);
    for(int i = 0; i < m; ++i) f[i] = Mul(f[i], f[i]);
    DFT(f, 1);
    for(int i = 0; i < m; ++i) g[i] = f[i].x * 1.0 / m + 0.5;
    LL ans = 0; mul = 1;
    for(int i = 1; i <= n; ++i) {
        if(val[i]) --g[mapp[val[i]] * 2];
    }
    for(int i = 0; i <= P - 2; ++i) {
        ans += mul * (g[i] + g[i + P - 1]) / 2;
        mul = mul * 2 % P;
    }
    cout << ans << endl;
    return 0;
}
```