#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ull unsigned long long
#define y1 ljhadglkjsadf
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter set< pair<int,ll> >::iterator
#define iter1 set<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=1e6+7;
const int inf=1e18+1e9;
const int mod=200003;
const int LEN=(1LL<<19);
const ld eps=1e-9;
double PI;

//const int MAX_MEM=1e8;
//int mpos=0;
//char mem[MAX_MEM];
//
//inline void * operator new(size_t n){
//    char *res=mem+mpos;
//    mpos+=n;
//    if (mpos>=MAX_MEM){
//        cout<<"BAD"<<endl;
//        exit(0);
//    }
//    return (void*)res;
//}
//
//inline void operator delete(void *) {}

int cnt[LEN],b[LEN],num[LEN];

typedef complex<ld> base;

void fft(vector<base>&a,bool invert)
{
    int n=(int)a.size();
    for (int i=1,j=0;i<n;++i){
        int bit=(n>>1);
        for (;j>=bit;bit>>=1){
            j-=bit;
        }
        j+=bit;
        if (i<j){
            swap(a[i],a[j]);
        }
    }
    for (int len=2;len<=n;len<<=1){
        ld ang=(2*PI/(ld)len);
        if (invert){
            ang*=-1;
        }
        base wlen (cos(ang),sin(ang));
        for (int i=0;i<n;i+=len){
            base w(1);
            for (int j=0;j<len/2;++j){
                base u=a[i+j];
                base v=a[i+j+len/2]*w;
                a[i+j]=u+v;
                a[i+j+len/2]=u-v;
                w=(w*wlen);
            }
        }
    }
    if (invert){
        for (int i=0;i<n;++i){
            a[i]/=(ld)n;
        }
    }
}

void multiply(vector<int>&a,vector<int>&b,vector<int>& res)
{
    vector<base>fa;
    for (int i=0;i<a.size();++i){
        base r(a[i]);
        fa.pb(r);
    }
    vector<base>fb;
    for (int i=0;i<b.size();++i){
        base r(b[i]);
        fb.pb(r);
    }
    fft(fa,0);
    fft(fb,0);
    for (int i=0;i<LEN;++i){
        fa[i]*=fb[i];
    }
    fft(fa,1);
    res.resize(LEN,0);
    for (int i=0;i<LEN;++i){
        res[i]=(int)(fa[i].real()+0.5);
    }
}

int powmod(int a,int b,int p)
{
    int res=1;
    a%=p;
    while(b){
        if (b%2==1){
            res=(res*a)%p;
        }
        a=(a*a)%p;
        b/=2;
    }
    return res;
}

int generator(int p)
{
    int phi=p-1;
    int n=phi;
    vector<int>fact;
    for (int i=2;i*i<=n;++i){
        if (n%i==0){
            fact.pb(i);
            while(n%i==0){
                n/=i;
            }
        }
    }
    if (n>1){
        fact.pb(n);
    }
    for (int res=2;res<p;++res){
        bool good=1;
        for (int i=0;i<fact.size();++i){
            if (powmod(res,n/fact[i],p)==1){
                good=0;
                break;
            }
        }
        if (good){
            return res;
        }
    }
    return -1;
}

main ()
{
    PI=acos(-1);
    ios;
    int c=generator(mod);
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>b[i];
        cnt[b[i]]++;
    }
    vector<int> a1(LEN,0);
    int cur=1;
    for (int i=0;i<mod-1;++i){
        a1[i]=cnt[cur];
//        if (cnt[cur]){
//            cout<<i<<' '<<cnt[cur]<<endl;
//        }
        cur=(cur*c)%mod;
    }
   // cout<<endl;
    vector<int>a2=a1;
    vector<int>res;
    multiply(a1,a2,res);
    for (int i=0;i<LEN;++i){
//        if (res[i]){
//            cout<<i<<' '<<res[i]<<endl;
//        }
    }
    int ans=0;
//    for (int i=1;i<=n;++i){
//        ans=(ans-(b[i]*b[i])%mod);
//    }
    for (int i=0;i<mod-1;++i){
        res[i+i]-=a1[i];
    }
   // cout<<endl;
    cur=1;
    for (int i=0;i<LEN;++i){
//        if (res[i]){
//            cout<<i<<' '<<res[i]<<endl;
//        }
        int gg=res[i];
        ans+=gg*cur/2;
        cur=(cur*c)%mod;
    }
    cout<<ans<<endl;
}
//8 4
//1 2 3 1 2 3 1 2
//1 2
//2 3
//4 5
//6 7


Measured memory_bytes: 55480