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;
using LL = long long;
using LD = long double;
constexpr int P = 200003;
constexpr int maxn = 1 << 19;
const double PI = acos(-1.);
int Log[P], Exp[P];
struct comp{
	double a, b;
	comp(double a = 0, double b = 0) : a(a), b(b){};
	comp operator + (const comp& x)const{return comp(a + x.a, b + x.b);}
	comp operator - (const comp& x)const{return comp(a - x.a, b - x.b);}
	comp operator * (const comp& x)const{return comp(a * x.a - b * x.b, a * x.b + b * x.a);}
	comp operator / (const int& x)const{return comp(a / x, b / x);}
	comp conj()const{return comp(a, -b);}
};
void FFT(comp* a, int n, bool inv = false){
	static int on = 0, rev[maxn];
	static comp w[maxn];
	if(on != n){
		for(int i = 0; i < n; i += 1){
			rev[i] = i ? rev[i >> 1] >> 1 | (i & 1 ? n >> 1 : 0) : 0;
			w[i] = comp(cos(PI / n * i), sin(PI / n * i));
		}
		on = n;
	}
	for(int i = 0; i < n; i += 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
	for(int m = 1; m <= n >> 1; m <<= 1)
		for(int j = 0; j < n; j += m << 1)
			for(int k = 0, p = 0; k < m; k += 1, p += n / m){
				comp tmp = (inv ? w[p].conj() : w[p]) * a[j + k + m];
				a[j + k + m] = a[j + k] - tmp;
				a[j + k] = a[j + k] + tmp;
			}
	if(inv) for(int i = 0; i < n; i += 1) a[i] = a[i] / n;
}
comp A[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    for(int i = 0; i + 1 < P; i += 1){
        Exp[i] = i ? Exp[i - 1] * 2 % P : 1;
        Log[Exp[i]] = i;
    }
    LL ans = 0;
    for(int i = 1, x; i <= N; i += 1){
        cin >> x;
        if(x) A[Log[x]].a += 1;
        ans -= (LL)x * x % P;
    }
    FFT(A, maxn);
    for(int i = 0; i < maxn; i += 1) A[i] = A[i] * A[i];
    FFT(A, maxn, true);
    for(int i = 0; i < maxn; i += 1)
        ans += (LL)(A[i].a + .5) * Exp[i % (P - 1)];
    cout << ans / 2;
    return 0;
}