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;

const int N = 8e5 + 5;
const int P = 200003;
const double PI = acos( -1.0 );
int _w;

struct Complex {
  double x , y;
  Complex( double x = 0 , double y = 0 ):
    x( x ) , y( y ) {}
  Complex operator + ( const Complex & rhs ) const {
    return Complex( x + rhs.x , y + rhs.y );
  }
  Complex operator - ( const Complex & rhs ) const {
    return Complex( x - rhs.x , y - rhs.y );
  }
  Complex operator * ( const Complex & rhs ) const {
    return Complex( x * rhs.x - y * rhs.y , x * rhs.y + y * rhs.x );
  }
} _wn[N] , f[N] , g[N];

int _r[N] , _now;
inline void _init( int n ) {
  if( _now == n ) return;
  _now = n; int l = 0; while( ( 1 << l ) < n ) ++l;
  --l; for( int i = 0 ; i < n ; ++i ) {
    _r[i] = ( _r[i >> 1] >> 1 ) | ( (i&1) << l );
    _wn[i] = Complex( cos( (2 * PI / n) * i ) , sin( (2 * PI / n) * i ) ); 
  }
}

void DFT( Complex * f , int n ) {
  static Complex x; _init( n );
  for( int i = 1 ; i < n ; ++i ) if( i < _r[i] ) swap( f[i] , f[_r[i]] );
  for( int mid = 1 , tk = n / 2 ; mid < n ; mid <<= 1 , tk >>= 1 ) 
    for( int i = 0 ; i < n ; i += ( mid << 1 ) ) 
      for( int j = 0 ; j < mid ; ++j ) {
        x = f[i + j + mid] * _wn[tk * j];
        f[i + j + mid] = f[i + j] - x;
        f[i + j] = f[i + j] + x;
      }
}

void IDFT( Complex * f , int n ) {
  reverse( f + 1 , f + n ); DFT( f , n );
  for( int i = 0 ; i < n ; ++i ) 
    f[i].x /= n , f[i].y /= n;
}

int n , dat[N] , LOG[N];
long long ans[N] , res;

int main( void ) {
  for( int i = 0 , now = 1 ; i < P - 1 ; ++i ) {
    LOG[now] = i;
    now = ( now + now ) % P;
  }
  _w = scanf("%d",&n);
  for( int i = 1 ; i <= n ; ++i ) {
    _w = scanf("%d",dat+i);
    if( dat[i] == 0 ) continue;
    dat[i] = LOG[dat[i]];
    --ans[dat[i] * 2];
    f[dat[i]].x += 1;
  }
  int lim = 1;
  while( lim < P + P ) lim <<= 1;
  DFT( f , lim ); 
  for( int i = 0 ; i < lim ; ++i ) g[i] = f[i] * f[i];
  IDFT( g , lim );
  for( int i = 0 , now = 1 ; i < P + P ; ++i ) {
    ans[i] += (long long)( g[i].x + 0.5 );
    res += ( ans[i] / 2 ) * now;
    now = ( now + now ) % P;
  }
  cout << res;
  return 0;
}