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:
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 524288
#define P 200003

static_assert(__builtin_popcount(N) == 1);
#define PRIME ((3u<<30)+1)
#define OMEGA (ntt_pow(5,PRIME/N))
constexpr uint ntt_pow(uint a, uint b)
{
    return !b ? 1 : (ulli)ntt_pow((ulli)a*a % PRIME, b>>1) * (b&1?a:1) % PRIME;
}
void ntt_rec(uint *a, int n, uint w)
{
    if(n==1) return;
    int n2 = n/2;
    uint w2 = ntt_pow(w,2);
    ntt_rec(a,n2,w2);
    ntt_rec(a+n2,n2,w2);
    uint k = 1;
    for(int i=0,j=n2;i<n2;++i,++j,k = (ulli)k * w % PRIME)
    {
        uint e = a[i], o = a[j];
        a[i] = ( e + (ulli)o*k ) % PRIME;
        a[j] = ( e + (ulli)PRIME*PRIME - (ulli)o*k ) % PRIME;
    }
}
uint ntt_bitreverse32(uint k)
{
    k = __builtin_bswap32(k);
    k = (((k & 0xf0f0f0f0) >> 4) | ((k & 0x0f0f0f0f) << 4));
    k = (((k & 0xcccccccc) >> 2) | ((k & 0x33333333) << 2));
    k = (((k & 0xaaaaaaaa) >> 1) | ((k & 0x55555555) << 1));
    return k;
}
void ntt(uint *a, int n=N, uint w=OMEGA)
{
    for(int i=0;i<n;++i)
    {
        int ii = ntt_bitreverse32(i) >> __builtin_clz(n)+1;
        if(i<ii) std::swap(a[i],a[ii]);
    }
    ntt_rec(a,n,w);
}
void ntt_inv(uint *a)
{
    ntt(a,N,ntt_pow(OMEGA,PRIME-2));
    for(int i=0;i<N;++i) a[i] = (ulli)a[i] * ntt_pow(N,PRIME-2) % PRIME;
}

int po[N], lo[N];
uint a[N], b[N];

int main()
{
    for(int i=0, k=1; i<P-1; ++i, k=k*2%P)
        po[i] = k, lo[k] = i;
    int n;
    lli ans = 0;
    scanf("%d", &n);
    for(int i=0;i<n;++i)
    {
        int k;
        scanf("%d", &k);
        if(!k) continue;
        ++a[lo[k]];
        ans -= (lli)k*k % P;
    }
    for(int i=0;i<N;++i) b[i] = a[i] % 13;
    ntt(a);
    for(int i=0;i<N;++i) a[i] = (ulli)a[i] * a[i] % PRIME;
    ntt_inv(a);
    ntt(b);
    for(int i=0;i<N;++i) b[i] = (ulli)b[i] * b[i] % PRIME;
    ntt_inv(b);
    for(int i=0;i<N;++i)
    {
        ans += po[i%(P-1)] * (a[i] + (lli)(b[i]+(PRIME+2)-a[i])*6%13 * PRIME);
        static_assert(((lli)PRIME*6) % 13 == 1);
        static_assert((PRIME+2) % 13 ==0);
    }
    assert(ans%2==0);
    ans /= 2;
    printf("%lld\n", ans);
    return 0;
}