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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using cmp=complex<double>;
const ll P=200003;
const int lg=19,N=1<<lg;
int n,vl[1<<18],rev[N];
ll ans,cnt[1<<18],rans;
cmp a[N],w[lg][N];
basic_string<int> v;
ll po(ll a,ll b,ll c){ll r=1;for(;b;b/=2,a=a*a%c)if(b&1)r=r*a%c;return r;}
void FFT(cmp*a){
	for(int i=0;i<N;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=0;i<lg;i++)
		for(int j=0;j<N;j++)if(j>>i&1){
			cmp l=a[j^1<<i],r=a[j]*w[i][j&(1<<i)-1];
			a[j^1<<i]=l+r,a[j]=l-r;
		}
}
int main(){
	scanf("%d",&n);
	for(int j=0;j<P-1;j++)vl[po(2,j,P)]=j;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		if(x)a[vl[x]]+=1.;
		ans-=1ll*x*x%P;
	}
	for(int i=0;i<N;i++)rev[i]=rev[i/2]/2|i%2<<lg-1;
	for(int i=0;i<lg;i++)
		for(int j=0;j<(1<<i);j++)w[i][j]=exp(acos(-1)*j/(1<<i)*cmp{0.,1.});
	FFT(a);
	for(int i=0;i<N;i++)a[i]=conj(a[i]*a[i]);
	FFT(a);double rv=1./N;
	for(int i=0;i<N;i++)
		cnt[i%(P-1)]+=ll(a[i].real()*rv+.5);
	for(int i=0;i<P-1;i++)
		rans+=cnt[i]*po(2,i,P);
	printf("%lld\n",(rans+ans)/2);
	return 0;
}