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;

typedef __int128 ll;
typedef long double ld;

const ll P = 75161927681ll;
const int N = (1 << 20);

inline ll add(ll x, ll y) {x += y; return x >= P ? x - P : x;}
inline ll sub(ll x, ll y) {x -= y; return x < 0 ? x + P : x;}
inline ll mul(ll x, ll y) {return x * y % P;}
ll mpow(ll b, ll p) {
    ll r; for(r = 1; p; p >>= 1, b = mul(b, b))
        if( p & 1 ) r = mul(r, b);
    return r;
}

#define rep(i, x, n) for(int i=x;i<n;i++)

ll w[N + 5], iv[N + 5]; int lg[N + 5];
void ntt(ll *A, int n, int type) {
	for(int i=0,j=0;i<n;i++) {
		if( i < j ) swap(A[i], A[j]);
		for(int k=(n>>1);(j^=k)<k;k>>=1);
	}
	for(int s=2,t,u,p;s<=n;s<<=1) {
		t = (s >> 1), u = N / s;
		for(int i=0;i<n;i+=s) {
			p = (type == 1 ? 0 : N); ll q = A[i + t];
			for(int j=0;j<t;j++,p=(type==1?p+u:p-u),q=mul(A[i+j+t],w[p]))
				A[i + j + t] = sub(A[i + j], q), A[i + j] = add(A[i + j], q);
		}
	}
	if( type == -1 ) rep(i, 0, n) A[i] = mul(A[i], iv[n]);
}

const int G = 2;
const int PK = 200003;

int ind[PK + 5], pw[PK + 5];

void init() {
	w[0] = iv[1] = 1, w[1] = mpow(3, (P - 1) / N);
	for(int i=2;i<=N;i++) {
		w[i] = mul(w[i - 1], w[1]), lg[i] = lg[(i + 1) >> 1] + 1;
		iv[i] = sub(0, mul(P / i, iv[P % i]));
	}
	
	for(int i=0,p=1;i<PK-1;p=G*p%PK,i++)
		ind[p] = i, pw[i] = p;
}

ll res[N + 5], cnt[N + 5];

int main() {
	init(); int n; scanf("%d", &n);
	for(int i=1,x;i<=n;i++) {
		scanf("%d", &x);
		if( x ) cnt[ind[x]]++;
	}
	int l = (1 << lg[PK + PK]);
	ntt(cnt, l, 1);
	for(int i=0;i<l;i++) res[i] = mul(cnt[i], cnt[i]);
	ntt(res, l, -1), ntt(cnt, l, -1);
	
	ll ans = 0;
	for(int i=0;i<=2*PK;i++)
		ans += res[i] * pw[i % (PK - 1)];
	for(int i=0;i<=PK;i++)
		ans -= cnt[i] * pw[(2 * i)%(PK - 1)];
	printf("%lld\n", (long long)(ans / 2));
}