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 <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <assert.h>
#include <cmath>
#include <deque>
#include <set>
#include <unordered_map>
#include <complex>
#include <fstream>
#include <map>
using namespace std;
using ll = long long;
using ld = long double;
const ll mxn = 2e5+10;
const ll P = 200003;
ll A[mxn], cnt[P];

using cd = complex<double>;
const double PI = acos(-1);

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

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

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

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

vector<ll> multiply(vector<ll> const& a, vector<ll> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    ll n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (ll i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<ll> result(n);
    for (ll i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

ll Map[P];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll n; cin>>n;
	for(ll i=0; i<n; i++) {
		cin>>A[i]; cnt[A[i]]++;
	}

	vector<ll> cnt_g(P-1, 0);

	cnt_g[0] = cnt[1]; ll pr = 1;
	for(ll i=1; i<P-1; i++) {
		pr*=2; pr%=P; cnt_g[i] = cnt[pr]; Map[pr] = i;
	}

	ll sum = 0; for(ll i=1; i<P; i++) sum+=cnt[i]; for(ll i=0; i<P-1; i++) sum-=cnt_g[i]; assert(sum==0);

	vector<ll> cnt_g2 = cnt_g;
	vector<ll> res = multiply(cnt_g, cnt_g2);

	for(int i=P-1; i<res.size(); i++) {
		ll tmp = res[i]; res[i] = 0;
		res[i-P+1]+=tmp;
	}

	for(ll i=0; i<n; i++) {
		if(A[i]==0) continue;
		res[Map[A[i]*A[i]%P]]--;
	}

	ll ans = 0; ll pow = 1;
	for(ll i=0; i<P-1; i++) {
		res[i]/=2;
		ans+=pow*res[i];
		pow*=2; pow%=P;
	}

	cout << ans << '\n';

	return 0;
}