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<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
typedef long long ll;
typedef unsigned un;
typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(int& a,int t){if(t>a)a=t;}
bool umin(ll& a,ll t){if(t<a)return a=t,1;return 0;}
#define MAXN 1000011
const double PI=acos(-1.0);
struct comp
{
    double a,b;
    comp(double _a=0,double _b=0){a=_a,b=_b;}
    comp operator +(comp t){return comp(a+t.a,b+t.b);}
    comp operator -(comp t){return comp(a-t.a,b-t.b);}
    comp operator *(comp t){return comp(a*t.a-b*t.b,a*t.b+b*t.a);}
}w[MAXN];
int status[MAXN];
void FFT(comp* a,int len,int type)
{
    for(int i=0;i<len;++i)
        if(status[i]>i)std::swap(a[status[i]],a[i]);
    for(int cur=1;cur<len;cur<<=1)
        for(int j=0;j<len;j+=cur<<1)
            for(int k=0;k<cur;++k)
            {
                comp t=w[len/cur*k];t.b*=type;
                comp x=a[j+k],y=t*a[j+cur+k];
                a[j+k]=x+y,a[j+cur+k]=x-y;
            }
}
ll lg[MAXN],c[MAXN];
comp f[MAXN];
int main()
{
    ll n=read(),p=200003,now=1,x,ans=0;
    for(int i=0;i<p;++i)
    {
        lg[now]=i;
        now=now*11%p;
    }
    for(int i=1;i<=n;++i)
    {
        x=read();
        if(!x)continue;
        ans-=x*x%p, ++f[lg[x]].a;
    }
    int len=1;
    while(len<=p+p)len<<=1;
    for(int i=0;i<len;++i)
        status[i]=(status[i>>1]>>1)+((i&1)*(len>>1)),w[i]=comp(cos(PI/len*i),sin(PI/len*i));
    FFT(f,len,1);
    for(int i=0;i<len;++i)f[i]=f[i]*f[i];
    FFT(f,len,-1);
    now=1;
    for(int i=0;i<len;++i)c[now]+=ll(f[i].a/len+0.5),now=now*11%p;
    for(int i=0;i<p;++i)ans+=i*c[i];
    printf("%lld",ans/2);
    return 0;
}