#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;


const double PI=acos(-1);
typedef complex<double> base;
inline void fft (vector<base> & 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) {
		double ang = 2*PI/len * (invert ? -1 : 1);
		base wlen(cos(ang), sin(ang));
		for (int i=0; i<n; i+=len) {
			base w(1);
			for (int j=0; j<len/2; ++j) {
				base 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;
}

// a, b => coefs to multiply,  res => resulting coefs
// a[0], b[0], res[0] = coef x^0
inline void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {//change res to ll if needed
	if(a.size() * b.size() <= 256) {
		res.resize(a.size() + b.size()+1, 0);
		for(int i = 0; i < (int)a.size(); i++)
			for(int j = 0; j < (int)b.size(); j++)
				res[i + j] += 1LL * a[i] * b[j];
		while(res.size()>1 && res.back() == 0) res.pop_back();
		return;
	}
	vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
	size_t n=1;
	while (n<max(a.size(),b.size())) n<<=1;
	n<<=1;
	fa.resize(n),fb.resize(n);
	fft (fa,false);  fft(fb,false);
	for (size_t i=0; i<n; ++i)
		fa[i]*=fb[i];
	fft (fa, true);
	res.resize (n);
	for(size_t i=0; i<n; ++i)
		res[i]=(int)(fa[i].real()>0 ? fa[i].real()+0.5 : fa[i].real()-0.5);
	while(res.size()>1 && res.back() == 0) res.pop_back();
}

const int p = 200003;
const int g = 2;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> arr;
	for(int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		if(val > 0) arr.push_back(val);
	}
	n = arr.size();

	vector<int> order(2*p,0);
	int powG = g;
	for(int i = 1; i < 2*p; ++i) {
		order[i] = powG;
		powG = (powG * g) % p;
	}
	vector<int> inv(p,0);
	for(int i = 1; i < p; ++i) {
		inv[order[i]] = i;
	}
	vector<int> cnts(p,0);
	for(int val : arr) {
		++cnts[inv[val]];
	}
	vector<int> product;
	multiply(cnts,cnts,product);
	int res = 0;
	for(int i = 0; i < product.size(); ++i) {
		res += order[i] * product[i];
	}
	for(int val : arr) {
		res -= (val*val)%p;
	}
	cout << res/2;
}

### 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 <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;


const double PI=acos(-1);
typedef complex<double> base;
inline void fft (vector<base> & 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) {
		double ang = 2*PI/len * (invert ? -1 : 1);
		base wlen(cos(ang), sin(ang));
		for (int i=0; i<n; i+=len) {
			base w(1);
			for (int j=0; j<len/2; ++j) {
				base 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;
}

// a, b => coefs to multiply,  res => resulting coefs
// a[0], b[0], res[0] = coef x^0
inline void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {//change res to ll if needed
	if(a.size() * b.size() <= 256) {
		res.resize(a.size() + b.size()+1, 0);
		for(int i = 0; i < (int)a.size(); i++)
			for(int j = 0; j < (int)b.size(); j++)
				res[i + j] += 1LL * a[i] * b[j];
		while(res.size()>1 && res.back() == 0) res.pop_back();
		return;
	}
	vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
	size_t n=1;
	while (n<max(a.size(),b.size())) n<<=1;
	n<<=1;
	fa.resize(n),fb.resize(n);
	fft (fa,false);  fft(fb,false);
	for (size_t i=0; i<n; ++i)
		fa[i]*=fb[i];
	fft (fa, true);
	res.resize (n);
	for(size_t i=0; i<n; ++i)
		res[i]=(int)(fa[i].real()>0 ? fa[i].real()+0.5 : fa[i].real()-0.5);
	while(res.size()>1 && res.back() == 0) res.pop_back();
}

const int p = 200003;
const int g = 2;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> arr;
	for(int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		if(val > 0) arr.push_back(val);
	}
	n = arr.size();

	vector<int> order(2*p,0);
	int powG = g;
	for(int i = 1; i < 2*p; ++i) {
		order[i] = powG;
		powG = (powG * g) % p;
	}
	vector<int> inv(p,0);
	for(int i = 1; i < p; ++i) {
		inv[order[i]] = i;
	}
	vector<int> cnts(p,0);
	for(int val : arr) {
		++cnts[inv[val]];
	}
	vector<int> product;
	multiply(cnts,cnts,product);
	int res = 0;
	for(int i = 0; i < product.size(); ++i) {
		res += order[i] * product[i];
	}
	for(int val : arr) {
		res -= (val*val)%p;
	}
	cout << res/2;
}

```