#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R = long double;
const R PI = acos(-1.0L);

const ll prime = 200003LL;
const ll root = 2LL;

using C = complex<R>;

// inline C mul (const C &a, const C &b) {
// 	const R ar = real(a);
// 	const R ai = imag(a);
// 	const R br = real(b);
// 	const R bi = imag(b);
	
// 	const C ret = C(
// 		ar * br - ai * bi,
// 		ar * bi + br * ai
// 	);

// 	return ret;
// }

void fft(vector<C> &a, bool inv) {
	const int n = a.size();
	const R sign = (inv ? -1.0 : 1.0);

	int rj = 0;
	rep(j, 1, n - 1) {
		for (int k = n >> 1; k > (rj ^= k); k >>= 1);
		if (j < rj) swap(a[j], a[rj]);
	}

	for (int m = 1; m < n; m <<= 1) {
		C wn = exp(C(0.0, sign * PI / m)), w = 1.0;
		rep(p, m) {
			for (int s = p; s < n; s += 2 * m) {
				C u = a[s];
				C v = a[s + m] *  w;
				a[s] = u + v, a[s + m] = u - v;
			}
			w *= wn;
		}
	}
	if (inv) rep(i, n) a[i] /= n;
}

vector<C> convolution(vector<C> a) {
	int fft_size = 1;
	while (fft_size < 2 * a.size()) fft_size <<= 1;

	a.resize(fft_size), fft(a, 0);
	
	vector<C> c(fft_size, 0.0);
	rep(i, fft_size) c[i] = a[i] * a[i];

	fft(c, 1);
	return c;
}

ll val2idx[prime];
ll idx2val[prime];

void init() {
	ll cur = root;
	rep(i, 1, prime) {
		val2idx[cur] = i;
		idx2val[i] = cur;
		cur = 1LL * cur * root % prime;
	}
}

int main(void){
	init();
	vector<ll> coef(prime, 0LL);

	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
		if(a[i] == 0) continue;
		coef[val2idx[a[i]] - 1]++;
	}

	vector<C> tmp_coef;
	for(auto &elem: coef) {
		tmp_coef.push_back(C(elem, 0.0));
	}

	vector<C> tmp_res = convolution(tmp_coef);
	vector<ll> res;
	for(auto &elem: tmp_res) {
		res.push_back(round(real(elem)));
	}


	ll ans = 0LL;
	rep(i, 2 * prime) {
		const ll modified_i = (i + 1)  % (prime - 1) + 1;
		ans += 1LL * res[i] * idx2val[modified_i];
	}

	rep(i, n) {
		ans -= 1LL * a[i] * a[i] % prime;
	}

	ans /= 2LL;
	cout << ans << endl;

	return 0;
}
### 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>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R = long double;
const R PI = acos(-1.0L);

const ll prime = 200003LL;
const ll root = 2LL;

using C = complex<R>;

// inline C mul (const C &a, const C &b) {
// 	const R ar = real(a);
// 	const R ai = imag(a);
// 	const R br = real(b);
// 	const R bi = imag(b);
	
// 	const C ret = C(
// 		ar * br - ai * bi,
// 		ar * bi + br * ai
// 	);

// 	return ret;
// }

void fft(vector<C> &a, bool inv) {
	const int n = a.size();
	const R sign = (inv ? -1.0 : 1.0);

	int rj = 0;
	rep(j, 1, n - 1) {
		for (int k = n >> 1; k > (rj ^= k); k >>= 1);
		if (j < rj) swap(a[j], a[rj]);
	}

	for (int m = 1; m < n; m <<= 1) {
		C wn = exp(C(0.0, sign * PI / m)), w = 1.0;
		rep(p, m) {
			for (int s = p; s < n; s += 2 * m) {
				C u = a[s];
				C v = a[s + m] *  w;
				a[s] = u + v, a[s + m] = u - v;
			}
			w *= wn;
		}
	}
	if (inv) rep(i, n) a[i] /= n;
}

vector<C> convolution(vector<C> a) {
	int fft_size = 1;
	while (fft_size < 2 * a.size()) fft_size <<= 1;

	a.resize(fft_size), fft(a, 0);
	
	vector<C> c(fft_size, 0.0);
	rep(i, fft_size) c[i] = a[i] * a[i];

	fft(c, 1);
	return c;
}

ll val2idx[prime];
ll idx2val[prime];

void init() {
	ll cur = root;
	rep(i, 1, prime) {
		val2idx[cur] = i;
		idx2val[i] = cur;
		cur = 1LL * cur * root % prime;
	}
}

int main(void){
	init();
	vector<ll> coef(prime, 0LL);

	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
		if(a[i] == 0) continue;
		coef[val2idx[a[i]] - 1]++;
	}

	vector<C> tmp_coef;
	for(auto &elem: coef) {
		tmp_coef.push_back(C(elem, 0.0));
	}

	vector<C> tmp_res = convolution(tmp_coef);
	vector<ll> res;
	for(auto &elem: tmp_res) {
		res.push_back(round(real(elem)));
	}


	ll ans = 0LL;
	rep(i, 2 * prime) {
		const ll modified_i = (i + 1)  % (prime - 1) + 1;
		ans += 1LL * res[i] * idx2val[modified_i];
	}

	rep(i, n) {
		ans -= 1LL * a[i] * a[i] % prime;
	}

	ans /= 2LL;
	cout << ans << endl;

	return 0;
}
```