#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = __int128;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

constexpr ll P = 200'003, MOD = (5019LL << 23) + 1;
constexpr int M = 19, N = 1<<M;
ll pw(ll a, ll b){
	ll ret = 1;
	do{
		if(b%2) ret = ret * a % MOD;
		a = a * a % MOD;
	}while(b/=2);
	return ret;
}
ll inv(ll a){
	return pw(a, MOD-2);
}
ll sqr(ll n){
	// srand(0);
	// ll g = 3;
	// while(pw(g, (MOD-1)/2) != MOD-1) g += 2;
	// printf("g = %lld\n", (long long)g);
	ll q = 5019, s = 23;
	assert(MOD-1 == q * (1LL << s));
	ll z = 5;
	assert(pw(z, (MOD-1)/2) == MOD-1);

	ll m = s, c = pw(z, q), t = pw(n, q), ret = pw(n, (q+1)/2);
	for(;;){
		if(t == 0){
			ret = 0;
			break;
		}
		if(t == 1) break;
		ll i = 1;
		while(pw(t, 1LL<<i) != 1) i++;
		ll b = pw(c, 1LL<<(m-i-1));
		m = i;
		c = b * b % MOD;
		t = t * c % MOD;
		ret = ret * b % MOD;
	}

	if(ret == 1) ret = MOD-1;
	assert(ret * ret % MOD == n);
	// DEBUG("sqr(%lld) = %lld\n", n, ret);
	return ret;
}

void prt(ll a[N]){
	REP(i, N) if(a[i]) DEBUG("%d: %lld\t", i, a[i]);
	DEBUG("\n");
}

int o[P];
ll a[N] = {}, b[N], d[N];

ll w[N] = {1};
ll *c = new ll[N];
void hoge(ll z, ll *a, ll *b){
	FOR(i, 1, N) w[i] = w[i-1] * z % MOD;
	// REP(i, N){
	// 	REP(j, N) DEBUG("%9lld ", w[i*j%N]);
	// 	DEBUG("\n");
	// }

	REP(i, N){
		int j = 0;
		REP(k, M) if(i&(1<<k)) j |= 1<<(M-k-1);
		b[i] = a[j];
	}

	REP(k, M){ // m = 32   k = 2
		int m = 1<<k; // group = 4
		REP(i, N / m / 2){
			REP(j, m){
				int jj = i*2*m + j;
				c[jj] = (b[jj] + w[j << (M-1-k)] * b[jj + m]) % MOD;
				c[jj + m] = (b[jj] + w[(j+m) << (M-1-k)] * b[jj+m]) % MOD;
				// DEBUG("c[%d] = [%d]%lld + (%d)%lld * [%d]%lld = %lld\n", 
				// 		jj, jj, b[jj], j<<(M-1-k), w[j << (M-1-k)], jj+m, b[jj + m], c[jj]);
				// DEBUG("c[%d] = [%d]%lld + (%d)%lld * [%d]%lld = %lld\n", 
				// 		jj+m, jj, b[jj], (j+m)<<(M-1-k), w[(j+m) << (M-1-k)], jj+m, b[jj+m], c[jj+m]);
			}
			// FOR(j, i*2*m, (i*2+1)*m){
			// 	c[j  ] = (b[j] + w[] * b[j+m]) % MOD;
			// 	c[j+m] = (z * b[j] + b[j+m]) % MOD;
			// }
		}
		// prt(c);
		z = z * z % MOD;
		REP(i, N) swap(b[i], c[i]);
	}
}

set<ll> s;

int main(){
	FOR(i, 2, P) s.emplace(i);
	ll x;
	for(;;){
		x = *s.begin();
		ll y = 1;
		REP(i, P-2){
			s.erase(y);
			y = y * x % P;
			if(y == 1) goto nxt;
		}
		assert(y * x % P == 1);
		break;
nxt:;
	}
	DEBUG("primitive root = %lld\n", x);
	ll y = 1;
	REP(i, P-1){
		o[y] = i;
		assert(i == 0 || y != 1);
		y = y * x % P;
	}
	assert(y == 1);
	{
		int n; scanf("%d", &n);
		REP(i, n){
			long long x; scanf("%lld", &x);
			if(x){
				DEBUG("%lld => %d\n", x, o[x]);
				a[o[x]]++;
			}
		}
	}

	ll z = 1;
	REP(i, M) z = sqr(z);
	DEBUG("Root = %lld\n", z);

	prt(a);
	hoge(inv(z), a, b);
	REP(i, N) b[i] = b[i] * b[i] % MOD;
	hoge(z, b, d);
	REP(i, N) b[i] = d[i] * inv(N) % MOD;
	prt(b);

	REP(i, P) b[2*i] -= a[i];
	prt(b);

	ll ans = 0;
	{
		ll y = 1;
		REP(i, N){
			if(b[i]) DEBUG("%d => %lld * %lld\n", i, b[i], y);
			ans += b[i] * y;
			y = y * x % P;
		}
	}
	ans /= 2;
	printf("%lld\n", (long long)ans);
}




Measured memory_bytes: 52968