#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })


#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
using vi = vector<int>;

namespace FFT { // from KACTL

typedef complex<double> C;
typedef vector<double> vd;

void fft(vector<C> &a, vector<C> &rt, vi& rev, int n) {
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
	}
}

vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n), rt(n, 1); vi rev(n);
	rep(i,0,n) rev[i] = (rev[i/2] | (i&1) << L) / 2;
	for (int k = 2; k < n; k *= 2) {
		C z[] = {1, polar(1.0, M_PI / k)};
		rep(i,k,2*k) rt[i] = rt[i/2] * z[i&1];
	}
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in, rt, rev, n);
	trav(x, in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out, rt, rev, n);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4*n);
	return res;
}

};

const ll MOD = 200003;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	vl e(MOD,-1);
	ll t = 1;
	FOR(i,0,MOD-1) e[t] = i, t = t*2 % MOD;
	// FOR(t,1,MOD) assert(e[t] != -1);
	
	ll n; cin >> n;
	
	vector<double> p(MOD-1);
	FOR(i,0,n) {
		ll a; cin >> a;
		if (a > 0) p[e[a]] += 1;
//		cout << e[a] << endl;
	}
	
	auto q = FFT::conv(p,p);

//	FOR(i,0,MOD-1) if (p[i]) cout << i << " " << p[i] << endl;
	
	vl cnt(MOD-1);
	FOR(i,0,sz(q)) cnt[i%(MOD-1)] += llround(q[i]);
	
//	cout << endl;
//	FOR(i,0,MOD-1) if (cnt[i]) cout << i << " " << cnt[i] << endl;

	FOR(i,0,MOD-1) cnt[(2*i)%(MOD-1)] -= p[i];
	
	FOR(i,0,MOD-1) {
		assert(cnt[i]%2 == 0);
		cnt[i] /= 2;
	}
//	cout << endl;
//	FOR(i,0,MOD-1) if (cnt[i]) cout << i << " " << cnt[i] << endl;

	t = 1;

	ll res = 0;
	FOR(i,0,MOD-1) {
		res += cnt[i]*t;
		t = t*2 % MOD;
	}
	cout << res << endl;
}


### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })


#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
using vi = vector<int>;

namespace FFT { // from KACTL

typedef complex<double> C;
typedef vector<double> vd;

void fft(vector<C> &a, vector<C> &rt, vi& rev, int n) {
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
	}
}

vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n), rt(n, 1); vi rev(n);
	rep(i,0,n) rev[i] = (rev[i/2] | (i&1) << L) / 2;
	for (int k = 2; k < n; k *= 2) {
		C z[] = {1, polar(1.0, M_PI / k)};
		rep(i,k,2*k) rt[i] = rt[i/2] * z[i&1];
	}
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in, rt, rev, n);
	trav(x, in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out, rt, rev, n);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4*n);
	return res;
}

};

const ll MOD = 200003;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	vl e(MOD,-1);
	ll t = 1;
	FOR(i,0,MOD-1) e[t] = i, t = t*2 % MOD;
	// FOR(t,1,MOD) assert(e[t] != -1);
	
	ll n; cin >> n;
	
	vector<double> p(MOD-1);
	FOR(i,0,n) {
		ll a; cin >> a;
		if (a > 0) p[e[a]] += 1;
//		cout << e[a] << endl;
	}
	
	auto q = FFT::conv(p,p);

//	FOR(i,0,MOD-1) if (p[i]) cout << i << " " << p[i] << endl;
	
	vl cnt(MOD-1);
	FOR(i,0,sz(q)) cnt[i%(MOD-1)] += llround(q[i]);
	
//	cout << endl;
//	FOR(i,0,MOD-1) if (cnt[i]) cout << i << " " << cnt[i] << endl;

	FOR(i,0,MOD-1) cnt[(2*i)%(MOD-1)] -= p[i];
	
	FOR(i,0,MOD-1) {
		assert(cnt[i]%2 == 0);
		cnt[i] /= 2;
	}
//	cout << endl;
//	FOR(i,0,MOD-1) if (cnt[i]) cout << i << " " << cnt[i] << endl;

	t = 1;

	ll res = 0;
	FOR(i,0,MOD-1) {
		res += cnt[i]*t;
		t = t*2 % MOD;
	}
	cout << res << endl;
}


```