#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 8e5 + 5 ; 
const int P = 200003 ; 
int n, m, R[N], g[N], ord[N], fc[N], f[N], c[N], tt[N], limit, L, num, cnt, ans[N] ; 
void Init( int x ) {
	limit = 1, L = 0 ; 
	while( limit <= x ) limit <<= 1, ++ L ;
	rep( i, 0, limit ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ;
}
const double Pi = acos( -1.0 ) ;
struct Complex {
	double x, y ; 
	Complex( double xx = 0, double yy = 0 ) { x = xx, y = yy ; }
} F[N], Q[N], C[N], A1[N], A2[N], B1[N], B2[N] ; 
Complex operator * ( Complex x, Complex y ) { return Complex( x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x ) ; }
Complex operator + ( Complex x, Complex y ) { return Complex( x.x + y.x, x.y + y.y ) ; }
Complex operator - ( Complex x, Complex y ) { return Complex( x.x - y.x, x.y - y.y ) ; }
Complex operator / ( Complex x, double y ) { return Complex(x.x / y, x.y / y ) ; }
void FFT( Complex *a, int type ) {
	for( int i = 0; i < limit; ++ i ) if( R[i] > i ) swap( a[R[i]], a[i] ) ;
	for( int k = 1; k < limit; k <<= 1 ) {
		Complex Dw = Complex( cos( Pi / k ), type * sin( Pi / k ) );	
		for( int i = 0; i < limit; i += ( k << 1 ) ) {
			Complex w = Complex( 1, 0 ) ;
			for( int j = i; j < i + k; ++ j, w = w * Dw ) {
				Complex Ny = w * a[j + k], Nx = a[j] ;
				a[j + k] = Nx - Ny,	a[j] = Nx + Ny ; 
			} 
		}
	}	
	if( type != 1 ) rep( i, 0, limit ) a[i] = a[i] / (double)limit ;
}
signed main()
{
	n = gi() ; 
	rep( i, 1, n ) c[i] = gi() ; 
	int gg = 2, ff = 1 ; cnt = 400 ; 
	for( re int i = 0; i < P - 1; ++ i ) {
		ord[ff] = i, fc[i] = ff, ff = ff * 2 % P ; 
	}
	int Ans = 0 ; 
	rep( i, 1, n ) if(c[i]) tt[ord[c[i]]] ++, Ans -= c[i] * c[i] % P ; 
	rep( i, 0, P ) A1[i].x = tt[i] / cnt, A2[i].x = tt[i] % cnt ; 
	rep( i, 0, P ) B1[i].x = tt[i] / cnt, B2[i].x = tt[i] % cnt ; 
	Init( 2 * P + 5 ), FFT( A1, 1 ), FFT( A2, 1 ), FFT( B1, 1 ), FFT( B2, 1 ) ; 
	num = cnt * cnt % P ; 
	rep( i, 0, limit ) F[i] = A1[i] * B1[i], Q[i] = ( A1[i] * B2[i] + A2[i] * B1[i] ), C[i] = A2[i] * B2[i] ; 
	FFT( F, -1 ), FFT( Q, -1 ), FFT( C, -1 ) ;
	rep( i, 0, limit ) {
		ans[i] = ( (int)(F[i].x + 0.5) * num + ( (int)(Q[i].x + 0.5) * cnt ) + (int)(C[i].x + 0.5) ) ; 
		Ans += ans[i] * fc[i % (P - 1)] ;
	}
	cout << Ans / 2 << endl ; 
	return 0;
}

### Prompt

Please create a solution in CPP to the following 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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 8e5 + 5 ; 
const int P = 200003 ; 
int n, m, R[N], g[N], ord[N], fc[N], f[N], c[N], tt[N], limit, L, num, cnt, ans[N] ; 
void Init( int x ) {
	limit = 1, L = 0 ; 
	while( limit <= x ) limit <<= 1, ++ L ;
	rep( i, 0, limit ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ;
}
const double Pi = acos( -1.0 ) ;
struct Complex {
	double x, y ; 
	Complex( double xx = 0, double yy = 0 ) { x = xx, y = yy ; }
} F[N], Q[N], C[N], A1[N], A2[N], B1[N], B2[N] ; 
Complex operator * ( Complex x, Complex y ) { return Complex( x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x ) ; }
Complex operator + ( Complex x, Complex y ) { return Complex( x.x + y.x, x.y + y.y ) ; }
Complex operator - ( Complex x, Complex y ) { return Complex( x.x - y.x, x.y - y.y ) ; }
Complex operator / ( Complex x, double y ) { return Complex(x.x / y, x.y / y ) ; }
void FFT( Complex *a, int type ) {
	for( int i = 0; i < limit; ++ i ) if( R[i] > i ) swap( a[R[i]], a[i] ) ;
	for( int k = 1; k < limit; k <<= 1 ) {
		Complex Dw = Complex( cos( Pi / k ), type * sin( Pi / k ) );	
		for( int i = 0; i < limit; i += ( k << 1 ) ) {
			Complex w = Complex( 1, 0 ) ;
			for( int j = i; j < i + k; ++ j, w = w * Dw ) {
				Complex Ny = w * a[j + k], Nx = a[j] ;
				a[j + k] = Nx - Ny,	a[j] = Nx + Ny ; 
			} 
		}
	}	
	if( type != 1 ) rep( i, 0, limit ) a[i] = a[i] / (double)limit ;
}
signed main()
{
	n = gi() ; 
	rep( i, 1, n ) c[i] = gi() ; 
	int gg = 2, ff = 1 ; cnt = 400 ; 
	for( re int i = 0; i < P - 1; ++ i ) {
		ord[ff] = i, fc[i] = ff, ff = ff * 2 % P ; 
	}
	int Ans = 0 ; 
	rep( i, 1, n ) if(c[i]) tt[ord[c[i]]] ++, Ans -= c[i] * c[i] % P ; 
	rep( i, 0, P ) A1[i].x = tt[i] / cnt, A2[i].x = tt[i] % cnt ; 
	rep( i, 0, P ) B1[i].x = tt[i] / cnt, B2[i].x = tt[i] % cnt ; 
	Init( 2 * P + 5 ), FFT( A1, 1 ), FFT( A2, 1 ), FFT( B1, 1 ), FFT( B2, 1 ) ; 
	num = cnt * cnt % P ; 
	rep( i, 0, limit ) F[i] = A1[i] * B1[i], Q[i] = ( A1[i] * B2[i] + A2[i] * B1[i] ), C[i] = A2[i] * B2[i] ; 
	FFT( F, -1 ), FFT( Q, -1 ), FFT( C, -1 ) ;
	rep( i, 0, limit ) {
		ans[i] = ( (int)(F[i].x + 0.5) * num + ( (int)(Q[i].x + 0.5) * cnt ) + (int)(C[i].x + 0.5) ) ; 
		Ans += ans[i] * fc[i % (P - 1)] ;
	}
	cout << Ans / 2 << endl ; 
	return 0;
}

```