#include<bits/stdc++.h>

	typedef long long ll;
using namespace std;

#include <complex>
namespace FFT{
	// blog.myungwoo.kr/54
	typedef complex<double> base;
 
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
 
	const double C_PI = acos(-1);
 
	void fft(vector <base> &a, bool invert){
		int n = sz(a);
		for(int i=0,j=0;i<n;++i) {
			if(i>j) swap(a[i],a[j]);
			for(int k=n>>1;(j^=k)<k;k>>=1);
		}
		for (int len=2;len<=n;len<<=1){
			double ang = 2*C_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++){
					if((j & 127) == 127)w = base(cos(ang * j), sin(ang * j));	//오차가 클 경우 이 빈도를 늘린다. cos, sin 함수는 시간 부담이 있으니 주의
					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;
		}
	}
 
	void multiply_big(const vector<int> &a,const vector<int> &b, vector <ll> &res){
		// 단순히 오차가 심해 구하지 못하는 경우
		// 결과값은 long long 범위 안
		int n = 1;
		while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
		vector <base> A(n), B(n);
		int L_BLOCK = 10;
		for(int i=0;i<n;i++) A[i] = (i < sz(a) ? base(a[i] & ((1<<L_BLOCK)-1), a[i] >> L_BLOCK) : base(0));
		for(int i=0;i<n;i++) B[i] = (i < sz(b) ? base(b[i] & ((1<<L_BLOCK)-1), b[i] >> L_BLOCK) : base(0));
		fft(A, false); fft(B, false);
		vector <base> f1(n), f2(n), f3(n), f4(n);
		for(int i=0;i<n;i++) {
			int j=(n-i)&(n-1);
			f2[i]=(A[i]+conj(A[j]))*base(0.5,0);
			f1[i]=(A[i]-conj(A[j]))*base(0,-0.5);
			f4[i]=(B[i]+conj(B[j]))*base(0.5,0);
			f3[i]=(B[i]-conj(B[j]))*base(0,-0.5);
		}
		for(int i=0;i<n;i++) {
			A[i]=f1[i]*f3[i]+f1[i]*f4[i]*base(0,1);
			B[i]=f2[i]*f4[i]*base(0,1)+f2[i]*f3[i];
		}
		fft(A, true); fft(B, true);
		res.resize(n);
		for(int i=0;i<n;i++) {
			ll g1=(ll)round(A[i].real());
			ll g2=(ll)round(A[i].imag());
			ll g3=(ll)round(B[i].real());
			ll g4=(ll)round(B[i].imag());
			res[i] = (g4 + ((g2+g3)<<(L_BLOCK)) + (g1<<(L_BLOCK<<1)));
		}
	}
}
int Z[201000], n, U[201000];
int main(){
    int i, j, Mod = 200003, G=0;
    for(i=2;;i++){
        int t=1;
        for(j=1;;j++){
            t=1ll*t*i%Mod;
            if(t==1)break;
        }
        if(j==Mod-1){
            G=i;
            break;
        }
    }
    long long t=1;
    for(i=1;i<=Mod-1;i++){
        t=t*G%Mod;
        Z[t] = i;
        U[i]=t;
    }
    U[0]=1;
    Z[1]=0;
    scanf("%d",&n);
    vector<int>P(200003);
    vector<ll>res;
    long long r=0;
    for(i=0;i<n;i++){
        int a;
        scanf("%d",&a);
        if(a==0)continue;
        P[Z[a]]++;
        r-=1ll*a*a%Mod;
    }
    FFT::multiply_big(P,P,res);
    for(i=0;i<res.size();i++){
        r += 1ll*res[i]*U[i%(Mod-1)];
    }
    r/=2;
    printf("%lld\n",r);
}
### Prompt

Please formulate 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>

	typedef long long ll;
using namespace std;

#include <complex>
namespace FFT{
	// blog.myungwoo.kr/54
	typedef complex<double> base;
 
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
 
	const double C_PI = acos(-1);
 
	void fft(vector <base> &a, bool invert){
		int n = sz(a);
		for(int i=0,j=0;i<n;++i) {
			if(i>j) swap(a[i],a[j]);
			for(int k=n>>1;(j^=k)<k;k>>=1);
		}
		for (int len=2;len<=n;len<<=1){
			double ang = 2*C_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++){
					if((j & 127) == 127)w = base(cos(ang * j), sin(ang * j));	//오차가 클 경우 이 빈도를 늘린다. cos, sin 함수는 시간 부담이 있으니 주의
					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;
		}
	}
 
	void multiply_big(const vector<int> &a,const vector<int> &b, vector <ll> &res){
		// 단순히 오차가 심해 구하지 못하는 경우
		// 결과값은 long long 범위 안
		int n = 1;
		while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
		vector <base> A(n), B(n);
		int L_BLOCK = 10;
		for(int i=0;i<n;i++) A[i] = (i < sz(a) ? base(a[i] & ((1<<L_BLOCK)-1), a[i] >> L_BLOCK) : base(0));
		for(int i=0;i<n;i++) B[i] = (i < sz(b) ? base(b[i] & ((1<<L_BLOCK)-1), b[i] >> L_BLOCK) : base(0));
		fft(A, false); fft(B, false);
		vector <base> f1(n), f2(n), f3(n), f4(n);
		for(int i=0;i<n;i++) {
			int j=(n-i)&(n-1);
			f2[i]=(A[i]+conj(A[j]))*base(0.5,0);
			f1[i]=(A[i]-conj(A[j]))*base(0,-0.5);
			f4[i]=(B[i]+conj(B[j]))*base(0.5,0);
			f3[i]=(B[i]-conj(B[j]))*base(0,-0.5);
		}
		for(int i=0;i<n;i++) {
			A[i]=f1[i]*f3[i]+f1[i]*f4[i]*base(0,1);
			B[i]=f2[i]*f4[i]*base(0,1)+f2[i]*f3[i];
		}
		fft(A, true); fft(B, true);
		res.resize(n);
		for(int i=0;i<n;i++) {
			ll g1=(ll)round(A[i].real());
			ll g2=(ll)round(A[i].imag());
			ll g3=(ll)round(B[i].real());
			ll g4=(ll)round(B[i].imag());
			res[i] = (g4 + ((g2+g3)<<(L_BLOCK)) + (g1<<(L_BLOCK<<1)));
		}
	}
}
int Z[201000], n, U[201000];
int main(){
    int i, j, Mod = 200003, G=0;
    for(i=2;;i++){
        int t=1;
        for(j=1;;j++){
            t=1ll*t*i%Mod;
            if(t==1)break;
        }
        if(j==Mod-1){
            G=i;
            break;
        }
    }
    long long t=1;
    for(i=1;i<=Mod-1;i++){
        t=t*G%Mod;
        Z[t] = i;
        U[i]=t;
    }
    U[0]=1;
    Z[1]=0;
    scanf("%d",&n);
    vector<int>P(200003);
    vector<ll>res;
    long long r=0;
    for(i=0;i<n;i++){
        int a;
        scanf("%d",&a);
        if(a==0)continue;
        P[Z[a]]++;
        r-=1ll*a*a%Mod;
    }
    FFT::multiply_big(P,P,res);
    for(i=0;i<res.size();i++){
        r += 1ll*res[i]*U[i%(Mod-1)];
    }
    r/=2;
    printf("%lld\n",r);
}
```