#include <iostream>
#include <vector>
#include <complex>
#include <tuple>

using namespace std;


const int P = 2e5 + 3;
int ep[P];
int inv[P];
using ll = long long;
using ld = double;
using base = complex <ld>;

const ld pi = acos(-1);

string A, B, C;
vector <ll> X, Y, Z;
ll n, m, ans;

void fft(vector <base> &A, bool f)
{
	int k = A.size(), i, j, l, t;
	base w, x, y; ld th;

	for(i = 1, j = 0; i < k; i ++){
		for(l = k >> 1; j >= l; l >>= 1) j -= l;
		j += l; if(i < j) swap(A[i], A[j]);
	}

	for(i = 1; i < k; i <<= 1, t --){
		th = (f? -pi : pi) / i;
		w = base(cos(th), sin(th));
		for(j = 0; j < k; j += i + i){
			for(l = 0; l < i; l ++){
				if(l & 2047) x *= w;
				else x = l? base(cos(th * l), sin(th * l)) : 1;
				y = x * A[l | i | j];
				A[l | i | j] = A[l | j] - y;
				A[l | j] += y;
			}
		}
	}

	if(f) for(i = 0; i < k; i ++){
		A[i] /= k;
	}
}

vector <ll> mult(vector <ll> &X, vector <ll> &Y)
{
	ll s, i, j;

	for(s = 1; s < X.size() + Y.size(); s <<= 1);

	vector <base> P(s), Q(s);
	vector <ll> Z(X.size() + Y.size() - 1);

	for(i = 0; i < X.size(); i ++){
		P[i] = base(X[i] >> 12, X[i] & 4095);
	}
	for(i = 0; i < Y.size(); i ++){
		Q[i] = base(Y[i] >> 12, Y[i] & 4095);
	}
	fft(P, 0); fft(Q, 0);

	for(i = 0; i + i <= s; i ++){
		j = i? s - i : 0;
		base v1 = P[i] + conj(P[j]), v2 = conj(P[i]) - P[j];
		tie(P[i], Q[i], P[j], Q[j]) = make_tuple(
			v1 * Q[i], conj(v2) * conj(Q[j]),
			conj(v1) * Q[j], -v2 * conj(Q[i]));
	}
	fft(P, 1); fft(Q, 1);

	for(i = 0; i < Z.size(); i ++){
		Z[i] = (((ll)round(P[i].real()) << 23) + ((ll)round(Q[i].real()) >> 1)
			+ ((ll)round(P[i].imag() + Q[i].imag()) << 11));
	}

	return Z;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    int arr[n];
    int t = 1; for(int i = 0; i < P - 1; ++i)
    {
        ep[i] = t;
        inv[t] = i;
        t *= 2; t %= P;
    }

    vector<long long> A(P - 1), B, ret;
    for(int i = 0; i < n; ++i)
    {
        int x; cin >> x;
        arr[i] = x;
        if(x) ++A[inv[x]];
    }
//    for(int i = 0; i < A.size(); ++i) if(A[i]) cout << i << ' ' << A[i] << endl;
    B = A;
    ret = mult(A, B);
    ret.push_back(0);

//    for(int i = 0; i < ret.size(); ++i) if(ret[i]) cout << i << ' ' << ret[i] << endl;

    long long ans = 0;
    for(int i = 0; i < P - 1; ++i)
    {
        ans += 1ll * ep[i] * (ret[i] + ret[i + P - 1]);
    }
    for(int i = 0; i < n; ++i)
    {
        ans -= 1ll * arr[i] * arr[i] % P;
    }
    cout << ans / 2;
    return 0;
}

### Prompt

Please formulate a cpp solution to 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 <vector>
#include <complex>
#include <tuple>

using namespace std;


const int P = 2e5 + 3;
int ep[P];
int inv[P];
using ll = long long;
using ld = double;
using base = complex <ld>;

const ld pi = acos(-1);

string A, B, C;
vector <ll> X, Y, Z;
ll n, m, ans;

void fft(vector <base> &A, bool f)
{
	int k = A.size(), i, j, l, t;
	base w, x, y; ld th;

	for(i = 1, j = 0; i < k; i ++){
		for(l = k >> 1; j >= l; l >>= 1) j -= l;
		j += l; if(i < j) swap(A[i], A[j]);
	}

	for(i = 1; i < k; i <<= 1, t --){
		th = (f? -pi : pi) / i;
		w = base(cos(th), sin(th));
		for(j = 0; j < k; j += i + i){
			for(l = 0; l < i; l ++){
				if(l & 2047) x *= w;
				else x = l? base(cos(th * l), sin(th * l)) : 1;
				y = x * A[l | i | j];
				A[l | i | j] = A[l | j] - y;
				A[l | j] += y;
			}
		}
	}

	if(f) for(i = 0; i < k; i ++){
		A[i] /= k;
	}
}

vector <ll> mult(vector <ll> &X, vector <ll> &Y)
{
	ll s, i, j;

	for(s = 1; s < X.size() + Y.size(); s <<= 1);

	vector <base> P(s), Q(s);
	vector <ll> Z(X.size() + Y.size() - 1);

	for(i = 0; i < X.size(); i ++){
		P[i] = base(X[i] >> 12, X[i] & 4095);
	}
	for(i = 0; i < Y.size(); i ++){
		Q[i] = base(Y[i] >> 12, Y[i] & 4095);
	}
	fft(P, 0); fft(Q, 0);

	for(i = 0; i + i <= s; i ++){
		j = i? s - i : 0;
		base v1 = P[i] + conj(P[j]), v2 = conj(P[i]) - P[j];
		tie(P[i], Q[i], P[j], Q[j]) = make_tuple(
			v1 * Q[i], conj(v2) * conj(Q[j]),
			conj(v1) * Q[j], -v2 * conj(Q[i]));
	}
	fft(P, 1); fft(Q, 1);

	for(i = 0; i < Z.size(); i ++){
		Z[i] = (((ll)round(P[i].real()) << 23) + ((ll)round(Q[i].real()) >> 1)
			+ ((ll)round(P[i].imag() + Q[i].imag()) << 11));
	}

	return Z;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    int arr[n];
    int t = 1; for(int i = 0; i < P - 1; ++i)
    {
        ep[i] = t;
        inv[t] = i;
        t *= 2; t %= P;
    }

    vector<long long> A(P - 1), B, ret;
    for(int i = 0; i < n; ++i)
    {
        int x; cin >> x;
        arr[i] = x;
        if(x) ++A[inv[x]];
    }
//    for(int i = 0; i < A.size(); ++i) if(A[i]) cout << i << ' ' << A[i] << endl;
    B = A;
    ret = mult(A, B);
    ret.push_back(0);

//    for(int i = 0; i < ret.size(); ++i) if(ret[i]) cout << i << ' ' << ret[i] << endl;

    long long ans = 0;
    for(int i = 0; i < P - 1; ++i)
    {
        ans += 1ll * ep[i] * (ret[i] + ret[i + P - 1]);
    }
    for(int i = 0; i < n; ++i)
    {
        ans -= 1ll * arr[i] * arr[i] % P;
    }
    cout << ans / 2;
    return 0;
}

```