#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
//#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void __read(T &a) { cin >> a; }
template<typename T, typename ... Args>
void __read(T &a, Args &... args) {cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T>
void outv(const T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion

const int P = 200'003;

using base = complex<double>;
const int LOG = 19;
const int N = 1 << LOG;
base w[N];
int inv[N];

void initialFFT() {
    for (int i = 1; i < N; ++i) {
        if (i % 2 == 1) {
            inv[i] = inv[i - 1] + N / 2;
        } else {
            inv[i] = inv[i >> 1] >> 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        double ang = 2 * M_PI * i / N;
        w[i] = base(cos(ang), sin(ang));
    }
}

void FFT(vector<base> &a) {
    for (int i = 0; i < N; ++i) {
        if (inv[i] < i) {
            swap(a[i], a[inv[i]]);
        }
    }
    for (int l = 0; l < LOG; l++) {
        int len = 1 << l;
        for (int i = 0; i < N; i += 2 * len) {
            for (int j = 0; j < len; ++j) {
                base v = a[i + j], u = a[i + j + len] * w[j << (LOG - l - 1)];
                a[i + j] = v + u;
                a[i + j + len] = v - u;
            }
        }
    }
}

VI mul(const VI &a, const VI &b) {
    vector<base> a1(N), a2(N), b1(N), b2(N);
    const int Q = 1000;
    for (int i = 0; i < a.size(); ++i) {
        a1[i] = a[i] % Q;
        a2[i] = a[i] / Q;
    }
    for (int i = 0; i < b.size(); ++i) {
        b1[i] = b[i] % Q;
        b2[i] = b[i] / Q;
    }
    FFT(a1);
    FFT(b1);
    FFT(a2);
    FFT(b2);
    vector<int> res(N);
    {
        vector<base> c(N);
        for (int i = 0; i < N; ++i) {
            c[i] = a1[i] * b1[i];
        }
        FFT(c);
        reverse(c.begin() + 1, c.end());
        for (int i = 0; i < N; ++i) {
            c[i] /= N;
            res[i] = static_cast<int>(c[i].real() + 0.5);
        }
    }
    {
        vector<base> c(N);
        for (int i = 0; i < N; ++i) {
            c[i] = a1[i] * b2[i] + a2[i] * b1[i];
        }
        FFT(c);
        reverse(c.begin() + 1, c.end());
        for (int i = 0; i < N; ++i) {
            c[i] /= N;
            res[i] += static_cast<int>(c[i].real() + 0.5) * Q;
        }
    }
    {
        vector<base> c(N);
        for (int i = 0; i < N; ++i) {
            c[i] = a2[i] * b2[i];
        }
        FFT(c);
        reverse(c.begin() + 1, c.end());
        for (int i = 0; i < N; ++i) {
            c[i] /= N;
            res[i] += static_cast<int>(c[i].real() + 0.5) * Q * Q;
        }
    }
    return res;
}


int32_t main() {
    initialFFT();
    VI g(P - 1);
    g[0] = 1;
    for (int i = 2; i < P; ++i) {
        g[1] = i;
        VI was(P);
        was[1] = 1;
        bool ok = true;
        for (int j = 1; ok && j + 1 < P; ++j) {
            g[j] = g[j - 1] * i % P;
            if (was[g[j]]) {
                ok = false;
            }
            was[g[j]] = 1;
        }
        if (ok) {
            break;
        }
    }
    VI r(P);
    for (int i = 0; i < g.size(); ++i) {
        r[g[i]] = i;
    }
    make(int, n);
    VI a(n);
    VI pol(P);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] != 0) {
            pol[r[a[i]]]++;
        }
    }
    VI c = mul(pol, pol);
    int ans = 0;
    for(int i = 0; i < c.size(); ++i){
        ans += g[i % (P - 1)] * c[i];
    }
    for(int i = 0; i < n; ++i){
        ans -= (a[i] * a[i]) % P;
    }
    ans /= 2;
    cout << ans;


    return 0;
}

Measured memory_bytes: 67416