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:
/*
 * @Author: RBQRBQ
 * @Date: 2020-09-19 15:18:05
 * @LastEditors: RBQRBQ
 * @LastEditTime: 2020-09-19 16:03:32
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
typedef pair<ll,ll> pii;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;ll f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        x=x*f;
    }
}
using namespace IO;
const ll maxn (2000000+10);
const double Pi=acos(-1.0);
#define re register
struct Complex
{
    double x,y;
    Complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[maxn],b[maxn],c[maxn];
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);}//不懂的看复数的运算那部分 
ll N,M;
ll l,r[maxn];
ll limit=1;
void fft(Complex *A,ll type)
{
    for(re ll i=0;i<limit;++i) 
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(re ll mid=1;mid<limit;mid<<=1)
    {
        Complex Wn(cos(Pi/mid),type*sin(Pi/mid)); 
        for(ll R=mid<<1,j=0;j<limit;j+=R)
        {
            Complex w(1,0);
            for(re ll k=0;k<mid;++k,w=w*Wn)
            {
                Complex x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}
/*
***Remember to clear the array ,limit and l!
for(ll i=0;i<=N;i++) read(a[i].x);
for(ll i=0;i<=M;i++) read(b[i].x);
limit=1,l=0;
while(limit<=N+M) limit<<=1,l++;
for(ll i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
fft(a,1);
fft(b,1);
for(ll i=0;i<=limit;;i++) c[i]=a[i]*b[i];
fft(c,-1);
for(ll i=0;i<=N+M;i++)
    printf("%d ",(ll)(a[i].x/limit+0.5));
*/
ll A[maxn];
ll mp[maxn];
const ll P(200003);
ll qpow(ll x,ll k,ll p=P) {
    ll ret=1;
    while(k){
        if(k&1)
            ret = ret*(ll)x%p;
        x=x*(ll)x%p;
        k>>=1;
    }
    return ret;
}
int main()
{
    ll n;
    read(n);
    ll cnt=0;
    for(re ll i=1;i<=n;i++)
    {
        ll x;
        read(x);
        if(x==0) continue;
        else A[++cnt]=x;
    }
    n=cnt;
    for(re ll i=0;i<=P-2;i++) mp[qpow(2,i)]=i;
    for(re ll i=1;i<=n;i++) a[mp[A[i]]].x++,b[mp[A[i]]].x++;
    N=M=P; 
    limit=1,l=0;
    while(limit<=N+M) limit<<=1,l++;
    for(ll i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1);
    fft(b,1);
    for(ll i=0;i<=limit;i++) c[i]=a[i]*b[i];
    fft(c,-1);
    for(ll i=0;i<=N+M;i++)
        c[i]=(ll)(c[i].x/limit+0.5);
    
    ll sum(0);
    for(ll i=0;i<=P-2;i++)
    {
        sum+=1ll*qpow(2,i)*(c[i].x+c[i+P-1].x);
    }
    ll sum2(0);
    for(ll i=1;i<=n;i++)
    sum2+=1ll*A[i]*A[i]%P;
    printf("%lld",(sum-sum2)/2);
    return 0;
}