#include<bits/stdc++.h>
using namespace std;
const int mod=200003;
typedef complex<double> comp;
typedef long long ll;
int n,a[200005],lg[200005],tr[600005],pw[600005];
ll ans=0;
comp s[600005],wk[600005];
void GetTr(int l) {
	for(int i=0; i<l; i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(l>>1):0);
}
void FFT(comp a[],int n,int flag){
	for(int i=0;i<n;i++)if(tr[i]<i)swap(a[i],a[tr[i]]);
	for(int i=1;i<n;i<<=1){
		wk[0]=1;
		if(flag==1)for(int j=1;j<i;j++)wk[j]=exp(comp(0,acos(-1)/i*j));
		else for(int j=1;j<i;j++)wk[j]=exp(comp(0,-acos(-1)/i*j));
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				comp t=a[i+j+k]*wk[k];
				a[i+j+k]=a[j+k]-t,a[j+k]+=t;
			}
		}
	}
	if(flag==-1)for(int i=0;i<n;i++)a[i]/=n;
}
int main() {
	for(int i=2,t=1;t<200003;i=i*2%mod,t++)lg[i]=t;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i])s[lg[a[i]]]+=1;
	}
	int len=524288;
	for(int i=0,t=1;i<len;i++,t=t*2%mod)pw[i]=t;
	GetTr(len),FFT(s,len,1);
	for(int i=0;i<len;i++)s[i]*=s[i];
	FFT(s,len,-1);
	for(int i=1;i<=n;i++)if(a[i])s[lg[a[i]]*2]-=1;
	for(int i=0;i<len;i++)s[i]/=2;
	for(int i=0;i<len;i++)ans+=pw[i]*(ll)(round(s[i].real()));
	cout<<ans;
	return 0;
}
### Prompt

Please create a solution in CPP 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;
const int mod=200003;
typedef complex<double> comp;
typedef long long ll;
int n,a[200005],lg[200005],tr[600005],pw[600005];
ll ans=0;
comp s[600005],wk[600005];
void GetTr(int l) {
	for(int i=0; i<l; i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(l>>1):0);
}
void FFT(comp a[],int n,int flag){
	for(int i=0;i<n;i++)if(tr[i]<i)swap(a[i],a[tr[i]]);
	for(int i=1;i<n;i<<=1){
		wk[0]=1;
		if(flag==1)for(int j=1;j<i;j++)wk[j]=exp(comp(0,acos(-1)/i*j));
		else for(int j=1;j<i;j++)wk[j]=exp(comp(0,-acos(-1)/i*j));
		for(int j=0;j<n;j+=(i<<1)){
			for(int k=0;k<i;k++){
				comp t=a[i+j+k]*wk[k];
				a[i+j+k]=a[j+k]-t,a[j+k]+=t;
			}
		}
	}
	if(flag==-1)for(int i=0;i<n;i++)a[i]/=n;
}
int main() {
	for(int i=2,t=1;t<200003;i=i*2%mod,t++)lg[i]=t;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i])s[lg[a[i]]]+=1;
	}
	int len=524288;
	for(int i=0,t=1;i<len;i++,t=t*2%mod)pw[i]=t;
	GetTr(len),FFT(s,len,1);
	for(int i=0;i<len;i++)s[i]*=s[i];
	FFT(s,len,-1);
	for(int i=1;i<=n;i++)if(a[i])s[lg[a[i]]*2]-=1;
	for(int i=0;i<len;i++)s[i]/=2;
	for(int i=0;i<len;i++)ans+=pw[i]*(ll)(round(s[i].real()));
	cout<<ans;
	return 0;
}
```