#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=300000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
const int p=200003;
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

struct Complex{
    double x,y;
    Complex(double _x=0.0,double _y=0.0) {x=_x;y=_y;}
};

Complex operator +(Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
Complex operator -(Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
Complex operator *(Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int r[N<<2];
Complex f[N<<2];

void fft(int lim,Complex *a,int typ)
{
    rep(i,0,lim-1)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (int mid=1;mid<lim;mid<<=1)
    {
        Complex wn=Complex(cos(pi/mid),sin(pi/mid)*typ);
        int len=(mid<<1);
        for (int sta=0;sta<lim;sta+=len)
        {
            Complex w=Complex(1,0);
            for (int j=0;j<mid;j++,w=w*wn)
            {
                Complex x=a[sta+j],y=a[sta+j+mid]*w;
                a[sta+j]=x+y;
                a[sta+j+mid]=x-y;
            }
        }
    }
}

int n,a[N],mp[N],cnt[N];

int main()
{
    n=read();
    int g=1;
    rep(i,0,p-2)
    {
        mp[g]=i;g=g*2%p;
    }
    rep(i,1,n)
    {
        a[i]=read();
        if (!a[i]) continue;
        int x=mp[a[i]];cnt[x]++;
        //cout << a[i] << " " << x << endl;
    }
    rep(i,0,p-1) f[i]=Complex(cnt[i],0);
    int lim=1,cnt=0;
    while (lim<(p<<1)) {lim<<=1;cnt++;}
    rep(i,0,lim-1) 
        r[i]=((r[i>>1]>>1)|((i&1)<<(cnt-1)));
    fft(lim,f,1);
    rep(i,0,lim-1) f[i]=f[i]*f[i];
    fft(lim,f,-1);
    g=1;ll ans=0;
    rep(i,0,(p-1)<<1)
    {
        ll now=(ll)(f[i].x/lim+0.5);
        ans+=now*g;
        g=g*2%p;
    }
    rep(i,1,n) ans-=1ll*a[i]*a[i]%p;
    ans/=2;
    printf("%lld",ans);
    return 0;
}


### Prompt

Construct a cpp code solution to the problem outlined:

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

### Response

```cpp
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=300000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
const int p=200003;
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

struct Complex{
    double x,y;
    Complex(double _x=0.0,double _y=0.0) {x=_x;y=_y;}
};

Complex operator +(Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
Complex operator -(Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
Complex operator *(Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int r[N<<2];
Complex f[N<<2];

void fft(int lim,Complex *a,int typ)
{
    rep(i,0,lim-1)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (int mid=1;mid<lim;mid<<=1)
    {
        Complex wn=Complex(cos(pi/mid),sin(pi/mid)*typ);
        int len=(mid<<1);
        for (int sta=0;sta<lim;sta+=len)
        {
            Complex w=Complex(1,0);
            for (int j=0;j<mid;j++,w=w*wn)
            {
                Complex x=a[sta+j],y=a[sta+j+mid]*w;
                a[sta+j]=x+y;
                a[sta+j+mid]=x-y;
            }
        }
    }
}

int n,a[N],mp[N],cnt[N];

int main()
{
    n=read();
    int g=1;
    rep(i,0,p-2)
    {
        mp[g]=i;g=g*2%p;
    }
    rep(i,1,n)
    {
        a[i]=read();
        if (!a[i]) continue;
        int x=mp[a[i]];cnt[x]++;
        //cout << a[i] << " " << x << endl;
    }
    rep(i,0,p-1) f[i]=Complex(cnt[i],0);
    int lim=1,cnt=0;
    while (lim<(p<<1)) {lim<<=1;cnt++;}
    rep(i,0,lim-1) 
        r[i]=((r[i>>1]>>1)|((i&1)<<(cnt-1)));
    fft(lim,f,1);
    rep(i,0,lim-1) f[i]=f[i]*f[i];
    fft(lim,f,-1);
    g=1;ll ans=0;
    rep(i,0,(p-1)<<1)
    {
        ll now=(ll)(f[i].x/lim+0.5);
        ans+=now*g;
        g=g*2%p;
    }
    rep(i,1,n) ans-=1ll*a[i]*a[i]%p;
    ans/=2;
    printf("%lld",ans);
    return 0;
}


```