	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	using namespace std;
	typedef long double D;
	const D pi = atan(1.0) * 4;
	int n , m;
	int l , half;
	const int MAXN = 6e5 + 10;
	int rev[MAXN];
	class Complex{
	public:
		D re , im;
		Complex (){}
		Complex (D _r , D _i) : re(_r) , im(_i) {}
		Complex operator+ (Complex u){
			return Complex(re + u.re , im + u.im);
		}
		Complex operator* (Complex b){
			return Complex(re * b.re - im * b.im , re * b.im + im * b.re);
		}
		Complex operator* (D p){
			return Complex(re * p , im * p);
		}
		Complex operator- (Complex u){
			return Complex(re - u.re , im - u.im);
		}
		Complex operator/ (D p){
			return Complex(re / p , im / p);
		}
		Complex conj(){
			return Complex(re , -im);
		}
		void fft(Complex *b , Complex *wu){
			fft_core(b , wu);
		}
		void ifft(Complex *b , Complex *wu){
			fft_core(b , wu);
			
			for(int i = 0 ; i < l ; ++ i)
				b[i] = b[i] / l;
		}
		void get_rev(Complex *b){
			for(int i = 0 ; i < l ; ++ i)
				if(rev[i] > i)
					swap(b[i] , b[rev[i]]);
		}
		void fft_core(Complex *b , Complex *wu){
			get_rev(b);
			for(int k = 1 ; k < l ; k <<= 1)
				for(int i = 0 ; i < l ; i += (k << 1))
					for(int j = 0 ; j < k ; ++ j){
						Complex tmp1 = b[i + j] , tmp2 = b[i + j + k] * wu[k + j];
						b[i + j] = tmp1 + tmp2;
						b[i + j + k] = tmp1 - tmp2;
			}
		}
	};
	
	Complex wu1[MAXN] , wu2[MAXN];
	Complex a[MAXN] , b[MAXN] , c[MAXN];
	void init(){
		l = 1;
		while(l <= n + m)
			l <<= 1;
		
		rev[0] = 0;
		half = (l >> 1);
		for(int i = 1 ; i < l ; ++ i)
			rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) ? half : 0));
		for(int i = half ; i < l ; ++ i)
			wu1[i] = Complex(cos(2 * pi * (i ^ half) / l) , sin(2 * pi * (i ^ half) / l));
		for(int i = half - 1 ; i >= 0 ; -- i)
			wu1[i] = wu1[i << 1];
		for(int i = 0 ; i < l ; ++ i)
			wu2[i] = wu1[i].conj();
	}
	
	const int MOD = 200003;
	int q[MAXN] , N;
	int w[MAXN] , g[MAXN];
	int fac[MAXN];
	int main(){
		ios::sync_with_stdio(false);
		int now = 1;
		for(int i = 0 ; i < MOD ; ++ i)
			q[i] = -1;
		for(int i = 0 ; i < MOD - 1 ; ++ i){
			q[now] = i;
			now = now * 2 % MOD;
		}
		fac[0] = 1;
		for(int i = 1 ; i < 2 * MOD ; ++ i)
			fac[i] = fac[i - 1] * 2 % MOD;
		cin >> N;
		long long ans = 0;
		for(int i = 1 ; i <= N ; ++ i){
			cin >> w[i];
			if(w[i] != 0)
				g[q[w[i]]] ++;
			ans -= 1ll * w[i] * w[i] % MOD;
		}
		n = MOD;
		m = MOD;
		for(int i = 0 ; i < MOD ; ++ i)
			b[i].re = a[i].re = g[i];
		init();
		Complex().fft(a , wu1);
		Complex().fft(b , wu1);
		for(int i = 0 ; i < l ; ++ i)
			c[i] = a[i] * b[i];
		Complex().ifft(c , wu2);
		for(int i = 0 ; i < 2 * MOD ; ++ i){
			long long x = (long long)(c[i].re + 0.5);
			ans = (ans + x * fac[i]);
		}
		cout << ans / 2 << endl;
		return 0;
	}
### Prompt

Construct a CPP code solution to the problem outlined:

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

### Response

```cpp
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	using namespace std;
	typedef long double D;
	const D pi = atan(1.0) * 4;
	int n , m;
	int l , half;
	const int MAXN = 6e5 + 10;
	int rev[MAXN];
	class Complex{
	public:
		D re , im;
		Complex (){}
		Complex (D _r , D _i) : re(_r) , im(_i) {}
		Complex operator+ (Complex u){
			return Complex(re + u.re , im + u.im);
		}
		Complex operator* (Complex b){
			return Complex(re * b.re - im * b.im , re * b.im + im * b.re);
		}
		Complex operator* (D p){
			return Complex(re * p , im * p);
		}
		Complex operator- (Complex u){
			return Complex(re - u.re , im - u.im);
		}
		Complex operator/ (D p){
			return Complex(re / p , im / p);
		}
		Complex conj(){
			return Complex(re , -im);
		}
		void fft(Complex *b , Complex *wu){
			fft_core(b , wu);
		}
		void ifft(Complex *b , Complex *wu){
			fft_core(b , wu);
			
			for(int i = 0 ; i < l ; ++ i)
				b[i] = b[i] / l;
		}
		void get_rev(Complex *b){
			for(int i = 0 ; i < l ; ++ i)
				if(rev[i] > i)
					swap(b[i] , b[rev[i]]);
		}
		void fft_core(Complex *b , Complex *wu){
			get_rev(b);
			for(int k = 1 ; k < l ; k <<= 1)
				for(int i = 0 ; i < l ; i += (k << 1))
					for(int j = 0 ; j < k ; ++ j){
						Complex tmp1 = b[i + j] , tmp2 = b[i + j + k] * wu[k + j];
						b[i + j] = tmp1 + tmp2;
						b[i + j + k] = tmp1 - tmp2;
			}
		}
	};
	
	Complex wu1[MAXN] , wu2[MAXN];
	Complex a[MAXN] , b[MAXN] , c[MAXN];
	void init(){
		l = 1;
		while(l <= n + m)
			l <<= 1;
		
		rev[0] = 0;
		half = (l >> 1);
		for(int i = 1 ; i < l ; ++ i)
			rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) ? half : 0));
		for(int i = half ; i < l ; ++ i)
			wu1[i] = Complex(cos(2 * pi * (i ^ half) / l) , sin(2 * pi * (i ^ half) / l));
		for(int i = half - 1 ; i >= 0 ; -- i)
			wu1[i] = wu1[i << 1];
		for(int i = 0 ; i < l ; ++ i)
			wu2[i] = wu1[i].conj();
	}
	
	const int MOD = 200003;
	int q[MAXN] , N;
	int w[MAXN] , g[MAXN];
	int fac[MAXN];
	int main(){
		ios::sync_with_stdio(false);
		int now = 1;
		for(int i = 0 ; i < MOD ; ++ i)
			q[i] = -1;
		for(int i = 0 ; i < MOD - 1 ; ++ i){
			q[now] = i;
			now = now * 2 % MOD;
		}
		fac[0] = 1;
		for(int i = 1 ; i < 2 * MOD ; ++ i)
			fac[i] = fac[i - 1] * 2 % MOD;
		cin >> N;
		long long ans = 0;
		for(int i = 1 ; i <= N ; ++ i){
			cin >> w[i];
			if(w[i] != 0)
				g[q[w[i]]] ++;
			ans -= 1ll * w[i] * w[i] % MOD;
		}
		n = MOD;
		m = MOD;
		for(int i = 0 ; i < MOD ; ++ i)
			b[i].re = a[i].re = g[i];
		init();
		Complex().fft(a , wu1);
		Complex().fft(b , wu1);
		for(int i = 0 ; i < l ; ++ i)
			c[i] = a[i] * b[i];
		Complex().ifft(c , wu2);
		for(int i = 0 ; i < 2 * MOD ; ++ i){
			long long x = (long long)(c[i].re + 0.5);
			ans = (ans + x * fac[i]);
		}
		cout << ans / 2 << endl;
		return 0;
	}
```