#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;

#define all(a) a.begin(), a.end()
#define pb push_back

struct comp {
    ld real, imag;
};

comp operator+(comp a, comp b) {
    return {a.real + b.real, a.imag + b.imag};
}

comp operator-(comp a, comp b) {
    return {a.real - b.real, a.imag - b.imag};
}

comp operator*(comp a, comp b) {
    return {a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real};
}

void operator*=(comp& a, comp b) {
    a = a * b;
}

void operator/=(comp& a, ld b) {
    a = {a.real / b, a.imag / b};
}

int rev(int num, int lg_n) {
    int res = 0;
    for (int i = 0; i < lg_n; i++) {
        if (num & (1<<i))
			res |= 1<<(lg_n-1-i);
    }
    return res;
}


ld PI = atan2(0, -1);
void fft (vector<comp> & a, bool invert) {
	int n = (int) a.size();
 
	for (int i=1, j=0; i<n; ++i) {
		int bit = n >> 1;
		for (; j>=bit; bit>>=1)
			j -= bit;
		j += bit;
		if (i < j)
			swap (a[i], a[j]);
	}
 
	for (int len=2; len<=n; len<<=1) {
		ld ang = 2*PI/len * (invert ? -1 : 1);
		comp wlen = {cos(ang), sin(ang)};
		for (int i=0; i<n; i+=len) {
			comp w = {1, 0};
			for (int j=0; j<len/2; ++j) {
			    comp u = a[i+j],  v = a[i+j+len/2] * w;
				a[i+j] = u + v;
				a[i+j+len/2] = u - v;
				w *= wlen;
			}
		}
	}
	if (invert)
		for (int i=0; i<n; ++i)
			a[i] /= n;
}

void solve() {
    ll p = 200003;
    vi kek(p);
    ll x = 1;
    for (int it = 0; it < p - 1; it++) {
        kek[x] = it;
        x *= 2;
        x %= p;
    }
    int n; cin >> n;
    vi a;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        if (x != 0) a.pb(x);
    }
    n = a.size();

    ll res = 0;
    for (auto& i : a) {
        res -= (i * i) % p;
    }

    for (auto& i : a) i = kek[i];

    int z = 524288;

    vector<comp> r(z);
    for (auto& i : a) r[i].real++;

    fft(r, 0);
    for (auto &i : r) i *= i;
    fft(r, 1);

    vi pow(p);
    for (int i = 1; i < p; i++) {
        pow[kek[i]] = i;
    }

    for (int i = 0; i < z; i++) {
        ll num = (ll)(r[i].real + .3);
        res += pow[i % (p - 1)] * num; 
    }
    cout << res / 2;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}
### Prompt

Develop a solution in cpp 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>

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;

#define all(a) a.begin(), a.end()
#define pb push_back

struct comp {
    ld real, imag;
};

comp operator+(comp a, comp b) {
    return {a.real + b.real, a.imag + b.imag};
}

comp operator-(comp a, comp b) {
    return {a.real - b.real, a.imag - b.imag};
}

comp operator*(comp a, comp b) {
    return {a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real};
}

void operator*=(comp& a, comp b) {
    a = a * b;
}

void operator/=(comp& a, ld b) {
    a = {a.real / b, a.imag / b};
}

int rev(int num, int lg_n) {
    int res = 0;
    for (int i = 0; i < lg_n; i++) {
        if (num & (1<<i))
			res |= 1<<(lg_n-1-i);
    }
    return res;
}


ld PI = atan2(0, -1);
void fft (vector<comp> & a, bool invert) {
	int n = (int) a.size();
 
	for (int i=1, j=0; i<n; ++i) {
		int bit = n >> 1;
		for (; j>=bit; bit>>=1)
			j -= bit;
		j += bit;
		if (i < j)
			swap (a[i], a[j]);
	}
 
	for (int len=2; len<=n; len<<=1) {
		ld ang = 2*PI/len * (invert ? -1 : 1);
		comp wlen = {cos(ang), sin(ang)};
		for (int i=0; i<n; i+=len) {
			comp w = {1, 0};
			for (int j=0; j<len/2; ++j) {
			    comp u = a[i+j],  v = a[i+j+len/2] * w;
				a[i+j] = u + v;
				a[i+j+len/2] = u - v;
				w *= wlen;
			}
		}
	}
	if (invert)
		for (int i=0; i<n; ++i)
			a[i] /= n;
}

void solve() {
    ll p = 200003;
    vi kek(p);
    ll x = 1;
    for (int it = 0; it < p - 1; it++) {
        kek[x] = it;
        x *= 2;
        x %= p;
    }
    int n; cin >> n;
    vi a;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        if (x != 0) a.pb(x);
    }
    n = a.size();

    ll res = 0;
    for (auto& i : a) {
        res -= (i * i) % p;
    }

    for (auto& i : a) i = kek[i];

    int z = 524288;

    vector<comp> r(z);
    for (auto& i : a) r[i].real++;

    fft(r, 0);
    for (auto &i : r) i *= i;
    fft(r, 1);

    vi pow(p);
    for (int i = 1; i < p; i++) {
        pow[kek[i]] = i;
    }

    for (int i = 0; i < z; i++) {
        ll num = (ll)(r[i].real + .3);
        res += pow[i % (p - 1)] * num; 
    }
    cout << res / 2;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}
```