#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
typedef complex<long double> C;

const int INF = 1e9 + 7, P = 200003, N = 1 << 19;
const long double TT = acosl(-1);

int e[P], cnt[P], b[P];

C a[N];

int pos[N];

void FFT(C* a, int k, int inv) {
	for(int i=1;i<(1<<k);i++) pos[i] = (pos[i >> 1] >> 1) | ((i & 1) << (k-1));
	for(int i=0;i<(1<<k);i++) if(i < pos[i]) swap(a[i], a[pos[i]]);
	for(int len=2;len<=(1<<k);len<<=1) {
		C w = C(cosl(2*TT/len), inv*sinl(2*TT/len));
		for(int i=0;i<(1<<k);i+=len) {
			C p = C(1, 0);
			for(int j=i;j<i+len/2;j++,p*=w) {
				C l = a[j], r = a[j+len/2];
				a[j] = l + p * r, a[j+len/2] = l - p * r;
			}
		}
	}
}

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	int ans = 0;
	for(int i = 0, pw = 1; i < P - 1; i++, pw = pw * 2 % P) e[pw] = i;
	for(int i = 0, x; i < n; i++) {
		cin >> x;
		if(x == 0) continue;
		cnt[e[x]]++, ans -= x * x % P;
	}
	for(int i = 0; i < P; i++) {
		a[i] = cnt[i];
	}
	FFT(a, 19, 1);
	for(int i = 0; i < N; i++) a[i] = a[i] * a[i];
	FFT(a, 19, -1);
	for(int i = 0; i < N; i++)
		b[i % (P-1)] += int(a[i].real()/N + 0.5);
	for(int i = 0, pw = 1; i < P-1; i++) ans += pw * b[i], pw = pw * 2 % P;
	ans /= 2;
	cout << ans << endl;
}




### Prompt

Develop a solution in CPP to the problem described below:

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 IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
typedef complex<long double> C;

const int INF = 1e9 + 7, P = 200003, N = 1 << 19;
const long double TT = acosl(-1);

int e[P], cnt[P], b[P];

C a[N];

int pos[N];

void FFT(C* a, int k, int inv) {
	for(int i=1;i<(1<<k);i++) pos[i] = (pos[i >> 1] >> 1) | ((i & 1) << (k-1));
	for(int i=0;i<(1<<k);i++) if(i < pos[i]) swap(a[i], a[pos[i]]);
	for(int len=2;len<=(1<<k);len<<=1) {
		C w = C(cosl(2*TT/len), inv*sinl(2*TT/len));
		for(int i=0;i<(1<<k);i+=len) {
			C p = C(1, 0);
			for(int j=i;j<i+len/2;j++,p*=w) {
				C l = a[j], r = a[j+len/2];
				a[j] = l + p * r, a[j+len/2] = l - p * r;
			}
		}
	}
}

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	int ans = 0;
	for(int i = 0, pw = 1; i < P - 1; i++, pw = pw * 2 % P) e[pw] = i;
	for(int i = 0, x; i < n; i++) {
		cin >> x;
		if(x == 0) continue;
		cnt[e[x]]++, ans -= x * x % P;
	}
	for(int i = 0; i < P; i++) {
		a[i] = cnt[i];
	}
	FFT(a, 19, 1);
	for(int i = 0; i < N; i++) a[i] = a[i] * a[i];
	FFT(a, 19, -1);
	for(int i = 0; i < N; i++)
		b[i % (P-1)] += int(a[i].real()/N + 0.5);
	for(int i = 0, pw = 1; i < P-1; i++) ans += pw * b[i], pw = pw * 2 % P;
	ans /= 2;
	cout << ans << endl;
}




```