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;

#define int long long

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

struct Template_FFT
{
	void fft(vector<cd> &a, bool invert)
	{
	    int n = a.size();
	
	    for (int i = 1, j = 0; i < n; i++)
	    {
	        int bit = n >> 1;
	        for (; j & bit; bit >>= 1)
	            j ^= bit;
	        j ^= bit;
	
	        if (i < j)
	            swap(a[i], a[j]);
	    }
	                                                   
	    for (int len = 2; len <= n; len <<= 1)
	    {
	        double ang = 2 * PI / len * (invert ? -1 : 1);
	        cd wlen(cos(ang), sin(ang));
	        for (int i = 0; i < n; i += len)
	        {
	            cd w(1);
	            for (int 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<int> multiply(vector<int> const& a, vector<int> const& b)
	{
		vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
		int n = 1;
		while(n < a.size() + b.size())
			n <<= 1;
		fa.resize(n);
		fb.resize(n);
	
		fft(fa, false);
		fft(fb, false);
	
		for (int i = 0; i < n; i++)
			fa[i] *= fb[i];
		fft(fa, true);
	
		vector<int> result(n);
		for (int i = 0; i < n; i++)
			result[i] = long(fa[i].real() + 0.5);
		return result;
	}
}FFT;	

const int mod = 200003;

int val_pow[200011], org[200011];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int g = 1;
	val_pow[1] = 0;
	org[0] = 1;
	for (int i = 1; i <= 200001; i++)
	{
		(g *= 2) %= mod;
		val_pow[g] = i;
		org[i] = g;
	}	

	int n;
	cin >> n;
	vector<int> a(200003), arr(200001);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		if (arr[i])
			a[val_pow[arr[i]]]++;
	}	
	vector<int> res = FFT.multiply(a, a); 	
	for (int i = 0; i < n; i++)
		if (arr[i])
			res[val_pow[arr[i]] + val_pow[arr[i]]]--;
	int ans = 0;
	for (int i = 0; i < 200003; i++)
		ans += org[i] * (res[i] + res[i + 200002]);
	cout << ans / 2;
}