#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define p_b push_back
#define SZ(x) ((ll)(x).size()) //size()がunsignedなのでエラー避けに
#define endk '\n'


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //

// 最小原始根 : ll MinimumPrimitiveRoot(ll p)
// 素数 p の原始根のうち、最小のものを返す
// 全ての原始根を求めたければ、最小原始根から芋づる式でいけるとのこと

ll modpow(ll x, ll n, ll mo){
  if ( n == 0 ) return 1;
  else{
    return modpow(x * x % mo, n / 2, mo) * (n % 2 ? x : 1) % mo;
  }
}

// prime_factorize(N): 素因数分解。vector<ll : 素因数>を返す。
// 1 は素数とされないので、1は入らない
// アルゴリズム上、自然と昇順で値が入るようになっている
// 恐らく O(√N)
vector<ll> prime_factorize(ll N) {
  vector<ll> res;
  for (ll a = 2; a * a <= N; ++a) {
    // 2～floor(√N)までが素因数の候補
    // なお、aが合成数となる場合もあるが、Nから既に約数として取り出されているため自然と無視され、素因数だけが入っていく。例えばa=4は合成数だが、a=2の時に割られているため、約数として判定されない。
    if (N % a != 0) continue;
    // ここから先、aはNの約数
    while (N % a == 0) {
      // aがNの約数でなくなるまで、aで割っていく
      // 約数でなくすのに要した回数が、素因数aの指数
      // ex) 約数として8があったのなら、2の約数でなくすのに3回要する = 2^3
        N /= a;
    }
    res.push_back(a); // {素因数, 指数}
  }
  // この時点で、Nは、√N以下の素因数aを全部ふるい出した状態になっている
  // まだN>1だとすると、それは√N以上の素因数があった場合か、元々のN自身が素数だった場合なので、ともかく現時点のNを素因数に加える
  if (N != 1) res.push_back(N);
  return res;
}

ll MinimumPrimitiveRoot(ll p){
  vector<ll> pfaclist = prime_factorize(p-1);
  ll len = (ll)pfaclist.size();
  ll a = 2;
  ll i = 0;
  while (i!=len){
    if (modpow(a, (p-1)/pfaclist[i], p) == 1){
      a += 1;
      i = 0;
    }
    else i += 1;
  }
  return a;
}


// 高速フーリエ変換（FFT）による畳み込み
// O( (N+M) * log(N+M) )
// https://ei1333.github.io/luzhiled/snippets/math/fast-fourier-transform.html
namespace FastFourierTransform {
  using real = double;

  struct C {
    real x, y;

    C() : x(0), y(0) {}

    C(real x, real y) : x(x), y(y) {}

    inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }

    inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }

    inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }

    inline C conj() const { return C(x, -y); }
  };

  const real PI = acosl(-1);
  int base = 1;
  vector< C > rts = { {0, 0},
                     {1, 0} };
  vector< int > rev = {0, 1};


  void ensure_base(int nbase) {
    if(nbase <= base) return;
    rev.resize(1 << nbase);
    rts.resize(1 << nbase);
    for(int i = 0; i < (1 << nbase); i++) {
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    }
    while(base < nbase) {
      real angle = PI * 2.0 / (1 << (base + 1));
      for(int i = 1 << (base - 1); i < (1 << base); i++) {
        rts[i << 1] = rts[i];
        real angle_i = angle * (2 * i + 1 - (1 << base));
        rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
      }
      ++base;
    }
  }

  void fft(vector< C > &a, int n) {
    assert((n & (n - 1)) == 0);
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for(int i = 0; i < n; i++) {
      if(i < (rev[i] >> shift)) {
        swap(a[i], a[rev[i] >> shift]);
      }
    }
    for(int k = 1; k < n; k <<= 1) {
      for(int i = 0; i < n; i += 2 * k) {
        for(int j = 0; j < k; j++) {
          C z = a[i + j + k] * rts[j + k];
          a[i + j + k] = a[i + j] - z;
          a[i + j] = a[i + j] + z;
        }
      }
    }
  }

  vector< int64_t > multiply(const vector< ll > &a, const vector< ll > &b) {
    int need = (int) a.size() + (int) b.size() - 1;
    int nbase = 1;
    while((1 << nbase) < need) nbase++;
    ensure_base(nbase);
    int sz = 1 << nbase;
    vector< C > fa(sz);
    for(int i = 0; i < sz; i++) {
      int x = (i < (int) a.size() ? a[i] : 0);
      int y = (i < (int) b.size() ? b[i] : 0);
      fa[i] = C(x, y);
    }
    fft(fa, sz);
    C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
    for(int i = 0; i <= (sz >> 1); i++) {
      int j = (sz - i) & (sz - 1);
      C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
      fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
      fa[i] = z;
    }
    for(int i = 0; i < (sz >> 1); i++) {
      C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
      C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
      fa[i] = A0 + A1 * s;
    }
    fft(fa, sz >> 1);
    vector< int64_t > ret(need);
    for(int i = 0; i < need; i++) {
      ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
    }
    return ret;
  }
};



// --------- library end - //


int main(){

  ll P = 200003;

  ll N;
  cin >> N;
  vector<ll> A(N);
  rep(i, N) cin >> A[i];

  // 全体を通して、Ai = 0 であるものは存在しないものとして考える
  // Ai=0ならAi*Aj=0であり、あってもなくても答えは同じで、無いほうが話が早いため


  // 200,003 の最小原始根（具体的には2）を r とする
  ll r = MinimumPrimitiveRoot(P);

  /* 解法

    rは原始根なので、r^1 mod p, r^2 mod p, r^3 mod p, ..., r^(p-1) mod p の中に、それぞれ 1 ~ p-1 が1個ずつ含まれている
    すると、Ai の範囲も同じく 1 ~ p-1（Ai=0は無視）なので、全ての Ai は「rの次数（1～p-1）」に一対一対応させることができる
    ということで、Ai を Ai≡r^Bi となるように一対一対応させた数列を、B とする

    ここで問題に戻り、Ai*Aj について考えてみる
    Ai≡r^Bi であるから、Ai*Aj≡(r^Bi)(r^Bj)=r^(Bi+Bj) と変形できる
    すると、Bi+Bj=k となるような ペア(i, j) の組の数が Lk とすれば、求めたい和は、Σ(k:0～p-1+p-1){r^(Bi+Bj) * Lk} であることが分かる

    この式は Lk（Bi+Bj=kとなるようなペアの数）さえ分かれば簡単に計算できるが、これは「和がKとなるような組み合わせの数」を求める問題なので、FFTを使った畳み込みで解くことができる。

  */

  
  // 数列 A -> 数列 B に変換するための配列を作る
  // AtoB[i] := i≡r^x となるような x（i=0のときは最終的に捨てるので何でもいいが、とりあえず区別をつけるため、AtoB[0]=0とする）
  vector<ll> AtoB(P);
  AtoB[0] = 0;
  ll tmp = 1;
  REP(i, 1, P){
    // i : 1 ~ P-1
    tmp = (tmp * r) % P;
    // tmp :=  tmp≡r^i
    AtoB[tmp] = i;
  }

  // A -> B
  vector<ll> B(N);
  rep(i, N) B[i] = AtoB[A[i]];


  // 畳み込みで解くために、「Bi:1~P-1となる要素がそれぞれいくつあるか」というバケツ配列に変換
  // ただし、Ai=0 であるものは無いものとして扱いたいので、Bi=0 であるものは無視する
  vector<ll> B_buckets(P);
  rep(i, N) if (B[i] != 0) B_buckets[B[i]]++;


  // FFTで畳み込む
  auto cs = FastFourierTransform::multiply(B_buckets, B_buckets);
  
  // r^k mod P を、0<=k<=2P-2 について求める
  vector<ll> r_k(2*P-2, 1);
  REP(i, 1, 2*P-1){
    r_k[i] = (r_k[i-1] * 2) % P;
  }

  // 答えを 各kについて ペア数 * r_k[i] で足し上げる
  ll ans = 0;
  rep(k, 2*P-1){
    ans += cs[k] * r_k[k];
  }

  // 同じペアを選んでしまっているパターン (Bi, Bi) を選んでしまっているパターンを取り除く
  // この時、k=bi+bi
  rep(bi, P){
    ans -= B_buckets[bi] * r_k[bi+bi];
  }
  
  // 非順序対なので(Bi, Bj)と(Bj, Bi)は同じものだが、別々に数えてしまっているので、/2しておく
  ans /= 2;


  cout << ans << endk;

}

Measured memory_bytes: 31648