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

const double pi = acos(-1);
struct cp {
	double x, y;
	cp operator+(cp a) { return { x + a.x,y + a.y }; }
	cp operator-(cp a) { return { x - a.x,y - a.y }; }
	cp operator*(cp a) { return { x*a.x - y * a.y,x*a.y + y * a.x }; }
};

const int maxn = 2100010;
int rev[maxn]; cp w[maxn];
void fft(cp x[], int len, int on) {

	for (int i = 0; i < len / 2; i++) {
		double alpha = 2 * pi*i / len;
		double c = cos(alpha), s = sin(alpha);
		w[i] = { c,s }; w[i + len / 2] = { -c,-s };
	}

	for (int i = 0; i < len; i++)rev[i] = (i & 1)*(len >> 1) + (rev[i >> 1] >> 1);
	for (int i = 0; i < len; i++)if (i < rev[i])swap(x[i], x[rev[i]]);
	for (int i = 2; i <= len; i <<= 1) {
		int wn = len / i, d = i >> 1;
		for (int j = 0; j < len; j += i) {
			int wk = 0;
			for (int k = j; k < j + d; k++) {
				cp a = x[k], b = w[wk] * x[k + d];
				x[k] = a + b, x[k + d] = a - b;
				wk += wn;
			}
		}
	}
	if (on == -1) {
		reverse(x + 1, x + len);
		for (int i = 0; i < len; i++)x[i].x /= len;
	}
}

// void work(cp x[], int n, cp y[], int m) {
// 	int len = 1;
// 	while (len <= n + m)len <<= 1;

// 	fft(x, len, 1); fft(y, len, 1);
// 	//这里是虚数的相乘不仅仅只是实部！！！
// 	for (int i = 0; i < len; i++)x[i] = x[i] * y[i];
// 	fft(x, len, -1);
// 	//有效长度n+m,请使用int(x+0.5)(负0),对于负数为int(x-0.5)
// 	for (int i = 0; i <= m + n; i++)cout << int(x[i].x + 0.5) << " "; cout << endl;
// }

cp a[maxn];
int x[maxn],y[maxn],base=5,mod=200003;
ll z[maxn];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	// int n, m; cin >> n >> m;
	// for (int i = 0; i <= n; i++)cin >> a[i].x;
	// for (int i = 0; i <= m; i++)cin >> b[i].x;
	// work(a, n, b, m);

    int now=1;
    for(int i=0;i<mod-1;i++){
        x[now]=i;
        now=now*base%mod;
    }
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int tmp;cin>>tmp;if(tmp==0)continue;
        y[x[tmp]]++;z[x[tmp]*2]--;
    }

    int len=1<<19;
    for(int i=0;i<len;i++) a[i].x=y[i];
    fft(a, len, 1);
    for(int i=0;i<len;i++) a[i]=a[i]*a[i];
    fft(a,len,-1);
    for(int i=0;i<len;i++) z[i]=(z[i]+(ll)(a[i].x + 0.5))/2;
    
    ll ans=0,now2=1;
    for(int i=0;i<len;i++){
        ans+=1ll*now2*z[i];
        now2=now2*base%mod;
    }
    cout<<ans<<endl;
}
### 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>
using namespace std;
#define ll long long

const double pi = acos(-1);
struct cp {
	double x, y;
	cp operator+(cp a) { return { x + a.x,y + a.y }; }
	cp operator-(cp a) { return { x - a.x,y - a.y }; }
	cp operator*(cp a) { return { x*a.x - y * a.y,x*a.y + y * a.x }; }
};

const int maxn = 2100010;
int rev[maxn]; cp w[maxn];
void fft(cp x[], int len, int on) {

	for (int i = 0; i < len / 2; i++) {
		double alpha = 2 * pi*i / len;
		double c = cos(alpha), s = sin(alpha);
		w[i] = { c,s }; w[i + len / 2] = { -c,-s };
	}

	for (int i = 0; i < len; i++)rev[i] = (i & 1)*(len >> 1) + (rev[i >> 1] >> 1);
	for (int i = 0; i < len; i++)if (i < rev[i])swap(x[i], x[rev[i]]);
	for (int i = 2; i <= len; i <<= 1) {
		int wn = len / i, d = i >> 1;
		for (int j = 0; j < len; j += i) {
			int wk = 0;
			for (int k = j; k < j + d; k++) {
				cp a = x[k], b = w[wk] * x[k + d];
				x[k] = a + b, x[k + d] = a - b;
				wk += wn;
			}
		}
	}
	if (on == -1) {
		reverse(x + 1, x + len);
		for (int i = 0; i < len; i++)x[i].x /= len;
	}
}

// void work(cp x[], int n, cp y[], int m) {
// 	int len = 1;
// 	while (len <= n + m)len <<= 1;

// 	fft(x, len, 1); fft(y, len, 1);
// 	//这里是虚数的相乘不仅仅只是实部！！！
// 	for (int i = 0; i < len; i++)x[i] = x[i] * y[i];
// 	fft(x, len, -1);
// 	//有效长度n+m,请使用int(x+0.5)(负0),对于负数为int(x-0.5)
// 	for (int i = 0; i <= m + n; i++)cout << int(x[i].x + 0.5) << " "; cout << endl;
// }

cp a[maxn];
int x[maxn],y[maxn],base=5,mod=200003;
ll z[maxn];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	// int n, m; cin >> n >> m;
	// for (int i = 0; i <= n; i++)cin >> a[i].x;
	// for (int i = 0; i <= m; i++)cin >> b[i].x;
	// work(a, n, b, m);

    int now=1;
    for(int i=0;i<mod-1;i++){
        x[now]=i;
        now=now*base%mod;
    }
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int tmp;cin>>tmp;if(tmp==0)continue;
        y[x[tmp]]++;z[x[tmp]*2]--;
    }

    int len=1<<19;
    for(int i=0;i<len;i++) a[i].x=y[i];
    fft(a, len, 1);
    for(int i=0;i<len;i++) a[i]=a[i]*a[i];
    fft(a,len,-1);
    for(int i=0;i<len;i++) z[i]=(z[i]+(ll)(a[i].x + 0.5))/2;
    
    ll ans=0,now2=1;
    for(int i=0;i<len;i++){
        ans+=1ll*now2*z[i];
        now2=now2*base%mod;
    }
    cout<<ans<<endl;
}
```