// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<ld,ld> pld;

const int maxn = (1<<19) + 10;

const ld pi=acos(-1);

pld operator +(pld a,pld b) {return {a.F+b.F,a.S+b.S};}
pld operator -(pld a,pld b) {return {a.F-b.F,a.S-b.S};}
pld operator *(pld a,pld b) {return {a.F*b.F-a.S*b.S,a.F*b.S+a.S*b.F};}
void operator/=(pld &a,ld b) { a.F/=b;a.S/=b;}

void fft(vector<pld> &a,bool rev){
    if(a.empty()) return;
    int n=32-__builtin_clz(sz(a));
    if(sz(a)==(1<<(n-1))) --n;
    a.resize((1<<n));
    
    for(int i=1;i<(1<<n);i++){
	int x=0;
	for(int j=0;j<n;j++)
	    if(bit(i,j)) x+=(1<<(n-1-j));
	if(i<x) swap(a[i],a[x]);
    }
    int N=(1<<n);
    for(int ln=0,Ln1=1,Ln2=2;ln<n;ln++,Ln1<<=1,Ln2<<=1){
	for(int start=0;start<N;start+=Ln2){
	    ld alpha=(rev?-1:1)*2*pi/Ln2;
	    pld w={cos(alpha),sin(alpha)},nw={1,0};
	    for(int i=start;i<start+Ln1;i++){
		pld &A=a[i],&B=a[i+Ln1],x=B*nw;
		nw=nw*w;
		B=A-x;A=A+x;
		if(rev)	B/=2,A/=2;
	    }
	}
    }
}

const int mod = 2e5 + 3;

int tolg[maxn], reallg[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int nw = 1;
    for(int i = 0; i < mod - 1; i++){
	reallg[i] = nw;
	tolg[nw] = i;
	nw = 2ll * nw % mod;
    }
    int n;
    cin >> n;
    vector<int> vec;
    vector<pld> ff(2 * mod);
    ll ans = 0;
    for(int i = 0; i < n; i++){
	int x;
	cin >> x;
	if(x == 0)
	    continue;
	ff[tolg[x]].F++;
	ans = (1ll * ans - 1ll * x * x % mod);
    }
    fft(ff, 0);
    for(int i = 0; i < sz(ff); i++)
	ff[i] = ff[i] * ff[i];
    fft(ff, 1);
    for(int i = 0; i < sz(ff); i++){
	ans+= 1ll * reallg[i % (mod-1)] * (ll(ff[i].F + 0.5));
    }
    ans/=2;
    return cout << ans << endl, 0;
}

### Prompt

Create a solution in Cpp for the following 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

### Response

```cpp
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<ld,ld> pld;

const int maxn = (1<<19) + 10;

const ld pi=acos(-1);

pld operator +(pld a,pld b) {return {a.F+b.F,a.S+b.S};}
pld operator -(pld a,pld b) {return {a.F-b.F,a.S-b.S};}
pld operator *(pld a,pld b) {return {a.F*b.F-a.S*b.S,a.F*b.S+a.S*b.F};}
void operator/=(pld &a,ld b) { a.F/=b;a.S/=b;}

void fft(vector<pld> &a,bool rev){
    if(a.empty()) return;
    int n=32-__builtin_clz(sz(a));
    if(sz(a)==(1<<(n-1))) --n;
    a.resize((1<<n));
    
    for(int i=1;i<(1<<n);i++){
	int x=0;
	for(int j=0;j<n;j++)
	    if(bit(i,j)) x+=(1<<(n-1-j));
	if(i<x) swap(a[i],a[x]);
    }
    int N=(1<<n);
    for(int ln=0,Ln1=1,Ln2=2;ln<n;ln++,Ln1<<=1,Ln2<<=1){
	for(int start=0;start<N;start+=Ln2){
	    ld alpha=(rev?-1:1)*2*pi/Ln2;
	    pld w={cos(alpha),sin(alpha)},nw={1,0};
	    for(int i=start;i<start+Ln1;i++){
		pld &A=a[i],&B=a[i+Ln1],x=B*nw;
		nw=nw*w;
		B=A-x;A=A+x;
		if(rev)	B/=2,A/=2;
	    }
	}
    }
}

const int mod = 2e5 + 3;

int tolg[maxn], reallg[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int nw = 1;
    for(int i = 0; i < mod - 1; i++){
	reallg[i] = nw;
	tolg[nw] = i;
	nw = 2ll * nw % mod;
    }
    int n;
    cin >> n;
    vector<int> vec;
    vector<pld> ff(2 * mod);
    ll ans = 0;
    for(int i = 0; i < n; i++){
	int x;
	cin >> x;
	if(x == 0)
	    continue;
	ff[tolg[x]].F++;
	ans = (1ll * ans - 1ll * x * x % mod);
    }
    fft(ff, 0);
    for(int i = 0; i < sz(ff); i++)
	ff[i] = ff[i] * ff[i];
    fft(ff, 1);
    for(int i = 0; i < sz(ff); i++){
	ans+= 1ll * reallg[i % (mod-1)] * (ll(ff[i].F + 0.5));
    }
    ans/=2;
    return cout << ans << endl, 0;
}

```