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;
const long long P = 200003;
const double PI = acos(-1);
long long modpow(long long a, long long b, long long M){
	long long ans = 1;
	while (b > 0){
		if (b % 2 == 1){
			ans *= a;
			ans %= M;
		}
		a *= a;
		a %= M;
		b /= 2;
	}
	return ans;
}
vector<complex<double>> fft(vector<complex<double>> A, bool inv){
	int N = A.size();
	int M = 0;
	for (int i = 1; i < N; i *= 2){
		M++;
	}
	for (int i = 0; i < N; i++){
		int j = 0;
		for (int k = 0; k < M; k++){
			if ((i >> k) & 1){
				j |= 1 << (M - 1 - k);
			}
		}
		if (i < j){
			swap(A[i], A[j]);
		}
	}
	for (int i = 1; i < N; i *= 2){
		for (int j = 0; j < i; j++){
			complex<double> z = polar((double) 1, (2 * PI) / (i * 2) * j * (inv ? -1 : 1));
			for (int k = 0; k < N; k += i * 2){
				complex<double> s = A[j + k];
				complex<double> t = A[j + k + i] * z;
				A[j + k] = s + t;
				A[j + k + i] = s - t;
			}
		}
	}
	if (inv){
		for (int i = 0; i < N; i++){
			A[i] /= N;
		}
	}
	return A;
}
vector<long long> convolution(vector<long long> A, vector<long long> B){
	int deg = A.size() + B.size() - 1;
	int N = 1;
	while (N < deg){
		N *= 2;
	}
	vector<complex<double>> A2(N);
	for (int i = 0; i < A.size(); i++){
		A2[i] = A[i];
	}
	while (A2.size() < N){
		A2.push_back(0);
	}
	vector<complex<double>> B2(N);
	for (int i = 0; i < B.size(); i++){
		B2[i] = B[i];
	}
	while (B2.size() < N){
		B2.push_back(0);
	}
	vector<complex<double>> a = fft(A2, false);
	vector<complex<double>> b = fft(B2, false);
	vector<complex<double>> c(N);
	for (int i = 0; i < N; i++){
		c[i] = a[i] * b[i];
	}
	c = fft(c, true);
	vector<long long> ans(deg);
	for (int i = 0; i < deg; i++){
		ans[i] = c[i].real() + 0.5;
	}
	return ans;
}
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<long long> B;
  for (int i = 0; i < N; i++){
    if (A[i] > 0){
      B.push_back(A[i]);
    }
  }
  N = B.size();
  vector<int> cnt(P, 0);
  for (int i = 0; i < N; i++){
    cnt[B[i]]++;
  }
  vector<long long> pow(P, 1);
  for (int i = 1; i < P; i++){
    pow[i] = pow[i - 1] * 2 % P;
  }
  vector<int> log(P);
  for (int i = 0; i < P - 1; i++){
    log[pow[i]] = i;
  }
  vector<long long> f(P - 1, 0);
  for (int i = 0; i < N; i++){
    f[log[B[i]]]++;
  }
  vector<long long> g = convolution(f, f);
  vector<long long> f2(P - 1, 0);
  for (int i = 0; i < g.size(); i++){
    f2[i % (P - 1)] += g[i];
  }
  long long ans = 0;
  for (int i = 0; i < P - 1; i++){
    ans += pow[i] * f2[i];
  }
  for (int i = 0; i < N; i++){
    ans -= B[i] * B[i] % P;
  }
  assert(ans % 2 == 0);
  ans /= 2;
  cout << ans << endl;
}