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>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn (1<<19)
//#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

typedef complex<double> cp;
const db pi=acos(-1.0);
int r[maxn*2+5],n2;

int BASE=2,P=200003;
int lg[maxn+5];
int cnt[maxn];
ll a[maxn+5];

cp W[maxn];

void FFT(cp a[],int opt)
{
    rep(i,1,n2-1) if(r[i]>i) swap(a[i],a[r[i]]);
    for(int step=1;step<n2;step<<=1)
    {
        rep(i,0,step-1)
        {
            W[i].real(cos(pi*i/step*opt));
            W[i].imag(sin(pi*i/step*opt));
        }
        //w.real(cos(sita)); w.imag(sin(sita));
        for(int step2=step<<1,i=0;i<n2;i+=step2)
        {
            //cp wj=1;
            rep(j,0,step-1)
            {
                cp even=a[i+j];
                cp odd=a[i+j+step];
                cp tmp=W[j]*odd;
                a[i+j]=even+tmp;
                a[i+j+step]=even-tmp;
            }
        }
    }
}

cp x[maxn];

int main()
{
    int t=1;
    ll ans=0;
    rep(i,1,P-1)
    {
        t=1ll*t*BASE%P;
        lg[t]=i;
    }

    int n; scanf("%d",&n);
    rep(i,1,n)
    {
        int x; scanf("%d",&x);
        cnt[lg[x]]++;
        //printf("?? %d\n",lg[x]);
        ans-=1ll*x*x%P;
    }
    int l=0;
    for(n2=1;n2<P*2;n2<<=1) l++;
    rep(i,1,n2-1) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
    rep(i,1,P-1) x[i]=cnt[i];
    FFT(x,1);
    rep(i,0,n2-1) x[i]=x[i]*x[i];
    FFT(x,-1);
    rep(i,0,n2-1) a[i]=x[i].real()/n2+0.5;
    rep(i,1,P-1) ans+=1ll*i*(a[lg[i]]+a[lg[i]+P-1]);
    assert(ans%2==0);
    printf("%lld\n",ans/2);
    return 0;
}