#include <bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

typedef complex<ld> cld;
typedef vector<cld> vc;

const int mod = 200003, MX = 4 * mod;
int n, a[MX], f[MX];
vc p(mod);

const ld pi = acos(ld(-1));
int rev[MX];
cld wlpw[MX];

void fft (vc& a, int n, bool inv) {
    for (int i = 0; i < n; i++ )
        if (i < rev[i])
            swap(a[i], a[rev[i]]);

    for (int len = 2; len <= n; len <<= 1) {
        ld ang = 2 * pi / len * (inv ? -1 : 1);
        cld wl (cos(ang), sin(ang));

        wlpw[0] = cld(1, 0);
        for (int i = 1; i < len / 2; i++)
            wlpw[i] = wlpw [i-1] * wl;
        
        cld t;
        int r, l;
        for (int i = 0; i < n; i += len) {
            for (int j = 0; j < len / 2; j++) {
                r = i + j + len / 2; l = i + j;
                t = a[r] * wlpw[j];
                a[r] = a[l] - t;
                a[l] += t ;
            }
        }
    }

    if (inv)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}
 
void obtRev ( int n, int log_n ) {
    for (int i = 0; i < n; i++) {
        rev[i] = 0 ;
        for (int j = 0; j < log_n; j++)
            if (i & (1 << j))
                rev[i] |= 1 << (log_n - 1 - j) ;
    }
}

void sq (vc &a) {
    int n = 1, ln = 0;

    while (n < a.size())
        n *= 2, ln++;
    n *= 2, ln++;
    obtRev(n, ln);

    a.resize(n);

    fft(a, n, 0);

    for (int i = 0; i < n; i++)
        a[i] *= a[i];

    fft(a, n, 1);

    for (int i = 0; i < n; i++) {
        a[i].real(ll(a[i].real() + 0.5));
        a[i].imag(0);
    }
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	ll acu = 1;
	forn (i, mod - 1) {
		f[acu] = i;
		(acu *= 2) %= mod;
	}
	
	cin >> n;

	forn (i, n) {
		cin >> a[i];
		if (!a[i]) continue;
		p[f[a[i]]] += 1;
	}

	sq(p);

	forn (i, n) {
		if (!a[i]) continue;
		p[2 * f[a[i]]] -= 1;
	}

	ll res = 0;
	acu = 1;

	forn (i, p.size()) {
		res += (ll)p[i].real() / 2 * acu;
		(acu *= 2) %= mod;
	}

	cout << res << endl;

	return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

typedef complex<ld> cld;
typedef vector<cld> vc;

const int mod = 200003, MX = 4 * mod;
int n, a[MX], f[MX];
vc p(mod);

const ld pi = acos(ld(-1));
int rev[MX];
cld wlpw[MX];

void fft (vc& a, int n, bool inv) {
    for (int i = 0; i < n; i++ )
        if (i < rev[i])
            swap(a[i], a[rev[i]]);

    for (int len = 2; len <= n; len <<= 1) {
        ld ang = 2 * pi / len * (inv ? -1 : 1);
        cld wl (cos(ang), sin(ang));

        wlpw[0] = cld(1, 0);
        for (int i = 1; i < len / 2; i++)
            wlpw[i] = wlpw [i-1] * wl;
        
        cld t;
        int r, l;
        for (int i = 0; i < n; i += len) {
            for (int j = 0; j < len / 2; j++) {
                r = i + j + len / 2; l = i + j;
                t = a[r] * wlpw[j];
                a[r] = a[l] - t;
                a[l] += t ;
            }
        }
    }

    if (inv)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}
 
void obtRev ( int n, int log_n ) {
    for (int i = 0; i < n; i++) {
        rev[i] = 0 ;
        for (int j = 0; j < log_n; j++)
            if (i & (1 << j))
                rev[i] |= 1 << (log_n - 1 - j) ;
    }
}

void sq (vc &a) {
    int n = 1, ln = 0;

    while (n < a.size())
        n *= 2, ln++;
    n *= 2, ln++;
    obtRev(n, ln);

    a.resize(n);

    fft(a, n, 0);

    for (int i = 0; i < n; i++)
        a[i] *= a[i];

    fft(a, n, 1);

    for (int i = 0; i < n; i++) {
        a[i].real(ll(a[i].real() + 0.5));
        a[i].imag(0);
    }
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	ll acu = 1;
	forn (i, mod - 1) {
		f[acu] = i;
		(acu *= 2) %= mod;
	}
	
	cin >> n;

	forn (i, n) {
		cin >> a[i];
		if (!a[i]) continue;
		p[f[a[i]]] += 1;
	}

	sq(p);

	forn (i, n) {
		if (!a[i]) continue;
		p[2 * f[a[i]]] -= 1;
	}

	ll res = 0;
	acu = 1;

	forn (i, p.size()) {
		res += (ll)p[i].real() / 2 * acu;
		(acu *= 2) %= mod;
	}

	cout << res << endl;

	return 0;
}

```