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>
#define maxn 600086
using namespace std; 

const double pi = acos(-1);

struct Complex{
	double x, y;
	Complex(double xx = 0, double yy = 0){
		x = xx, y = yy;
	}
};

Complex operator + (Complex a, Complex b){
	return Complex(a.x + b.x, a.y + b.y);
}

Complex operator - (Complex a, Complex b){
	return Complex(a.x - b.x, a.y - b.y);
}

Complex operator * (Complex a, Complex b){
	return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

int pos[maxn];//蝴蝶变换 

void FFT(Complex *a, int lim, int type){
	for(int i = 0;i < lim;i++){
		pos[i] = (pos[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);//相当于翻转后的i>>1是i的后缀 再判断一下最低位如果是1就翻转到最高位 
		if(i < pos[i]) swap(a[i], a[pos[i]]);//对应二进制翻转 因此有pos[pos[i]] = i 保证位置交换正确 
	}
	for(int mid = 1;mid < lim;mid <<= 1){//区间半长 n/2
		Complex wn(cos(pi / mid), type * sin(pi / mid));//一个单位根的跨度 
		for(int i = mid << 1, j = 0;j < lim;j += i){//i是区间全场 j是当前区间左端点 
			Complex w(1, 0);//单位根
			for(int k = 0;k < mid;k++, w = w * wn){//枚举左半部分 右半部分O(1)获得 
				Complex x = a[j + k], y = w * a[j + k + mid];
				a[j + k] = x + y;
				a[j + k + mid] = x - y;
			} 
		}
	}
	if(type == -1) for(int i = 0;i < lim;i++) a[i].x /= lim;
} 

const int p = 200003;

int n, x;
int f[maxn], g[maxn], cnt[maxn];
Complex a[maxn];

int main(){
	scanf("%d", &n);
	for(int i = 0, j = 1;i <= p - 2;i++, j = 2 * j % p) f[i] = j, g[j] = i;
	for(int i = 1;i <= n;i++){
		scanf("%d", &x);
		if(x) cnt[g[x]]++, a[g[x]].x++;
	}
	int lim = 1;
	while(lim <= 2 * p) lim <<= 1;
	FFT(a, lim, 1);
	for(int i = 0;i < lim;i++) a[i] = a[i] * a[i];
	FFT(a, lim, -1);
	for(int i = 0;i <= p - 2;i++) a[i * 2].x -= cnt[i];
	long long ans = 0;
	for(int i = 0;i < lim;i++) ans += f[i % (p - 1)] * (long long)(a[i].x / 2 + 0.5);
	printf("%lld", ans);
}