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;
typedef long double db;
typedef long long ll;
const int maxlogn=19;
const int maxn=(1<<maxlogn)|1;
const db tau=2*acosl(-1);
int n,m,rev[maxn];
struct comp
{
    db a,b;
    comp(db a=0,db b=0):a(a),b(b) {}
    inline comp operator +(const comp &x) const { return comp(a+x.a,b+x.b); }
    inline comp operator -(const comp &x) const { return comp(a-x.a,b-x.b); }
    inline comp operator *(const comp &x) const { return comp(a*x.a-b*x.b,a*x.b+b*x.a); }
}w[maxn];
inline void calcrev(int logn)
{
    int i;
    for(rev[0]=0,i=1;i<(1<<logn);i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(logn-1));
}
inline void init()
{
    int i;
    for(i=0;i<=(1<<maxlogn);i++)
        w[i]=comp(cosl(i*tau/(1<<maxlogn)),sinl(i*tau/(1<<maxlogn)));
}
inline void DFT(comp *a,int logn,bool flag)
{
    register int i,j,k,mid;
    comp x,y;
    for(i=0;i<(1<<logn);i++)
        if(rev[i]<i)
            swap(a[rev[i]],a[i]);
    for(i=1;i<=logn;i++)
        for(mid=1<<(i-1),j=0;j<(1<<logn);j+=1<<i)
            for(k=0;k<mid;k++)
            {
                x=a[j|k],y=a[j|k|mid]*w[flag?(1<<maxlogn)-(k<<(maxlogn-i)):(k<<(maxlogn-i))];
                a[j|k]=x+y,a[j|k|mid]=x-y;
            }
}
comp a[maxn];//b[maxn],c[maxn];
inline long long rnd(db x) { return (long long)(x+.5); }
inline void MTT(const ll *f,ll *h,int logn)
{
    int i;
    comp x,y,z;
    calcrev(logn);
    // for(i=0;i<(1<<logn);i++) a[i]=comp(f[i]>>16),b[i]=comp(f[i]&0xffff);//c[i]=comp(g[i]>>16),d[i]=comp(g[i]&0xffff);
    // DFT(a,logn,0),DFT(b,logn,0);//DFT(c,logn,0),DFT(d,logn,0);
    // for(i=0;i<(1<<logn);i++)
    //     x=a[i]*a[i],y=a[i]*b[i]*2,z=b[i]*b[i],a[i]=x,b[i]=y,c[i]=z;
    // DFT(a,logn,1),DFT(b,logn,1),DFT(c,logn,1);
    // for(i=0;i<(1<<logn);i++) a[i].a/=1<<logn,b[i].a/=1<<logn,c[i].a/=1<<logn;
    // for(i=0;i<(1<<logn);i++) h[i]=(((rnd(a[i].a))<<32)+((rnd(b[i].a))<<16)+rnd(c[i].a));
    for(i=0;i<(1<<logn);i++) a[i]=comp(f[i]);
    DFT(a,logn,0);
    for(i=0;i<(1<<logn);i++) a[i]=a[i]*a[i];
    DFT(a,logn,1);
    for(i=0;i<(1<<logn);i++) a[i].a/=1<<logn;
    for(i=0;i<(1<<logn);i++) h[i]=rnd(a[i].a);
}
const int kcz=200003;
ll cnt[kcz<<2],temp[kcz],ans[kcz<<2];
int logn;
int main()
{
    int a,n,i;
    init();
    ll t,s=0;
    for(temp[t=1]=i=0,i++;i<kcz-1;i++)
        t=t*2%kcz,assert(temp[t]==0),temp[t]=i;
    scanf("%d",&n);
    memset(cnt,0,sizeof(cnt));
    while(n--) { scanf("%d",&a); if(a) cnt[temp[a]]++; s-=a*(ll)a%kcz; }
    for(logn=0;(1<<logn)<(kcz<<1);logn++);
    MTT(cnt,ans,logn);
    for(t=1,i=0;i<kcz-1;t=t*2%kcz,i++)
        s+=(ans[i]+ans[i+kcz-1])*t;
    printf("%lld\n",s/2);
    return 0;
}