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

#define ll long long
#define ar array

template<typename T> struct cp {
	T x, y;
	cp<T> operator+(const cp &o) const {
		return {x+o.x, y+o.y};
	}
	cp<T> operator*(const cp &o) const {
		return {x*o.x-y*o.y, x*o.y+y*o.x};
	}
};
template<typename T> struct fft {
	static const int mxN=1<<19;
	cp<T> rt[mxN];
	void fi(int n) {
		T PI=acos((T)-1);
		for(int i=0; i<n/2; ++i) {
			T an=2*PI*i/n;
			rt[i+n/2]={cos(an), sin(an)};
		}
		for(int i=n/2; --i; )
			rt[i]=rt[2*i];
	}
	void ac(vector<cp<T>> &a) {
		int n=a.size();
		for(int i=0, j=0; i<n; ++i) {
			if(i>j)
				swap(a[i], a[j]);
			for(int k=n/2; (j^=k)<k; k/=2);
		}
		for(int st=1; 2*st<=n; st*=2) {
			for(int i=0; i<n; i+=2*st) {
				for(int j=i; j<i+st; ++j) {
					cp<T> z=rt[j-i+st]*a[j+st];
					a[j+st]=a[j]+cp<T>{-1, 0}*z;
					a[j]=a[j]+z;
				}
			}
		}
	}
	void mul(vector<cp<T>> &g, vector<cp<T>> &h) {
		int n=g.size();
		ac(g);
		for(int i=0; i<n; ++i) {
			int j=(n-i)&(n-1);
			cp<T> g2=g[i]*g[i];
			g2.x=-g2.x;
			h[i]=(g[j]*g[j]+g2)*cp<T>{(T)0, (T)-1/4/n};
		}
		ac(h);
	}
};
fft<long double> f;

const int P=200003;
int n, x[P], y[P];
vector<cp<long double>> c1(1<<19), c2(1<<19);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//*
	//set<int> s;
	int p=1;
	for(int i=0; i<P-1; ++i, p=p*2%P) {
		x[i]=p;
		y[p]=i;
		//s.insert(p);
	}
	//cout << s.size() << endl;
	//*/
	cin >> n;
	ll ans=0;
	for(int i=0; i<n; ++i) {
		int b;
		cin >> b;
		if(b) {
			++c1[y[b]].x;
			++c1[y[b]].y;
			//cout << b << " " << y[b] << endl;
			ans-=(ll)b*b%P;
			//cout << y[b]*2
		}
	}
	f.fi(1<<19);
	f.mul(c1, c2);
	for(int i=0; i<1<<19; ++i) {
		//if((ll)round(c2[i].x))
			//cout << i%P << " " << c2[i].x << endl;
		ans+=(ll)round(c2[i].x)*x[i%(P-1)];
	}
	cout << ans/2;
}
### Prompt

Create a solution in Cpp for 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;

#define ll long long
#define ar array

template<typename T> struct cp {
	T x, y;
	cp<T> operator+(const cp &o) const {
		return {x+o.x, y+o.y};
	}
	cp<T> operator*(const cp &o) const {
		return {x*o.x-y*o.y, x*o.y+y*o.x};
	}
};
template<typename T> struct fft {
	static const int mxN=1<<19;
	cp<T> rt[mxN];
	void fi(int n) {
		T PI=acos((T)-1);
		for(int i=0; i<n/2; ++i) {
			T an=2*PI*i/n;
			rt[i+n/2]={cos(an), sin(an)};
		}
		for(int i=n/2; --i; )
			rt[i]=rt[2*i];
	}
	void ac(vector<cp<T>> &a) {
		int n=a.size();
		for(int i=0, j=0; i<n; ++i) {
			if(i>j)
				swap(a[i], a[j]);
			for(int k=n/2; (j^=k)<k; k/=2);
		}
		for(int st=1; 2*st<=n; st*=2) {
			for(int i=0; i<n; i+=2*st) {
				for(int j=i; j<i+st; ++j) {
					cp<T> z=rt[j-i+st]*a[j+st];
					a[j+st]=a[j]+cp<T>{-1, 0}*z;
					a[j]=a[j]+z;
				}
			}
		}
	}
	void mul(vector<cp<T>> &g, vector<cp<T>> &h) {
		int n=g.size();
		ac(g);
		for(int i=0; i<n; ++i) {
			int j=(n-i)&(n-1);
			cp<T> g2=g[i]*g[i];
			g2.x=-g2.x;
			h[i]=(g[j]*g[j]+g2)*cp<T>{(T)0, (T)-1/4/n};
		}
		ac(h);
	}
};
fft<long double> f;

const int P=200003;
int n, x[P], y[P];
vector<cp<long double>> c1(1<<19), c2(1<<19);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//*
	//set<int> s;
	int p=1;
	for(int i=0; i<P-1; ++i, p=p*2%P) {
		x[i]=p;
		y[p]=i;
		//s.insert(p);
	}
	//cout << s.size() << endl;
	//*/
	cin >> n;
	ll ans=0;
	for(int i=0; i<n; ++i) {
		int b;
		cin >> b;
		if(b) {
			++c1[y[b]].x;
			++c1[y[b]].y;
			//cout << b << " " << y[b] << endl;
			ans-=(ll)b*b%P;
			//cout << y[b]*2
		}
	}
	f.fi(1<<19);
	f.mul(c1, c2);
	for(int i=0; i<1<<19; ++i) {
		//if((ll)round(c2[i].x))
			//cout << i%P << " " << c2[i].x << endl;
		ans+=(ll)round(c2[i].x)*x[i%(P-1)];
	}
	cout << ans/2;
}
```