#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define double long double
#define INF 2000000000
#define INF2 2000000000000000000
 
using namespace std;
using cd = complex<double>;

const double PI = acos(-1);
const int mod = 200003;
const int primitive = 2;

int power(int x, int y) {
	if(y == 0)
		return 1;
	int a = power(x, y/2);
	a = (1LL * a * a)%mod;
	if(y%2)
		a = (1LL * a * x)%mod;
	return a;
}

void fft(vector<cd> & a, bool invert) 
{
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) 
    {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) 
    {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) 
        {
            cd w(1);
            for (int j = 0; j < len / 2; j++) 
            {
                cd 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 (cd & x : a)
            x /= n;
    }
}

void selfMultiply(vector<ll> &a) {

	vector<cd>fa(a.begin(), a.end());
	int n = 2*(a.size()) - 1;
	int N = 1;
	while(N < n)
		N *= 2;
	fa.resize(N, 0);
	fft(fa, false);	
	for(int i = 0; i < N; i++)
		fa[i] *= fa[i];
	fft(fa, true);
	fa.resize(n);
	a.resize(n, 0);
	for(int i = 0; i < n; i++)
		a[i] = round(fa[i].real());

}

int main() {
    
    IOS;
    int n;
    cin >> n;
    int freq[mod];
    memset(freq, 0, sizeof(freq));
    for(int i = 1; i <= n; i++) {
    	int x;
    	cin >> x;
    	freq[x]++;
    }
    vector<ll>polynomial(mod - 1, 0);
    for(int i = 0; i < mod - 1; i++) {
    	int val = power(primitive, i);
    	polynomial[i] = freq[val];
    }
    selfMultiply(polynomial);
   	ll sum = 0;
   	for(int i = 0; i < polynomial.size(); i++) {
   		ll val = polynomial[i];
   		val *= power(primitive, i);
   		sum += val;
   	}	
   	for(int i = 0; i < mod; i++) {
   		ll val = (1LL * i * i)%mod;
   		val *= freq[i];
   		sum -= val;
   	}
   	sum /= 2;
   	cout << sum;
}
### 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>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define double long double
#define INF 2000000000
#define INF2 2000000000000000000
 
using namespace std;
using cd = complex<double>;

const double PI = acos(-1);
const int mod = 200003;
const int primitive = 2;

int power(int x, int y) {
	if(y == 0)
		return 1;
	int a = power(x, y/2);
	a = (1LL * a * a)%mod;
	if(y%2)
		a = (1LL * a * x)%mod;
	return a;
}

void fft(vector<cd> & a, bool invert) 
{
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) 
    {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) 
    {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) 
        {
            cd w(1);
            for (int j = 0; j < len / 2; j++) 
            {
                cd 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 (cd & x : a)
            x /= n;
    }
}

void selfMultiply(vector<ll> &a) {

	vector<cd>fa(a.begin(), a.end());
	int n = 2*(a.size()) - 1;
	int N = 1;
	while(N < n)
		N *= 2;
	fa.resize(N, 0);
	fft(fa, false);	
	for(int i = 0; i < N; i++)
		fa[i] *= fa[i];
	fft(fa, true);
	fa.resize(n);
	a.resize(n, 0);
	for(int i = 0; i < n; i++)
		a[i] = round(fa[i].real());

}

int main() {
    
    IOS;
    int n;
    cin >> n;
    int freq[mod];
    memset(freq, 0, sizeof(freq));
    for(int i = 1; i <= n; i++) {
    	int x;
    	cin >> x;
    	freq[x]++;
    }
    vector<ll>polynomial(mod - 1, 0);
    for(int i = 0; i < mod - 1; i++) {
    	int val = power(primitive, i);
    	polynomial[i] = freq[val];
    }
    selfMultiply(polynomial);
   	ll sum = 0;
   	for(int i = 0; i < polynomial.size(); i++) {
   		ll val = polynomial[i];
   		val *= power(primitive, i);
   		sum += val;
   	}	
   	for(int i = 0; i < mod; i++) {
   		ll val = (1LL * i * i)%mod;
   		val *= freq[i];
   		sum -= val;
   	}
   	sum /= 2;
   	cout << sum;
}
```