#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

#include <iostream>
#include <vector>
#include <complex>

using namespace std;

typedef long double DOUBLE;
typedef complex<DOUBLE> COMPLEX;
typedef vector<DOUBLE> VD;
typedef vector<int> VI;
typedef vector<COMPLEX> VC;

struct FFT {
  VC A;
  int n, L;

  int ReverseBits(int k) {
    int ret = 0;
    for (int i = 0; i < L; i++) {
      ret = (ret << 1) | (k & 1);
      k >>= 1;
    }
    return ret;
  }

  void BitReverseCopy(VC a) {
    for (n = 1, L = 0; n < a.size(); n <<= 1, L++) ;
    A.resize(n);
    for (int k = 0; k < n; k++) 
      A[ReverseBits(k)] = a[k];
  }
  
  VC DFT(VC a, bool inverse) {
    BitReverseCopy(a);
    for (int s = 1; s <= L; s++) {
      int m = 1 << s;
      COMPLEX wm = exp(COMPLEX(0, 2.0 * M_PI / m));
      if (inverse) wm = COMPLEX(1, 0) / wm;
      for (int k = 0; k < n; k += m) {
	COMPLEX w = 1;
	for (int j = 0; j < m/2; j++) {
	  COMPLEX t = w * A[k + j + m/2];
	  COMPLEX u = A[k + j];
	  A[k + j] = u + t;
	  A[k + j + m/2] = u - t;
	  w = w * wm;
	}
      }
    }
    if (inverse) for (int i = 0; i < n; i++) A[i] /= n;
    return A;
  }

  // c[k] = sum_{i=0}^k a[i] b[k-i]
  VD Convolution(VD a, VD b) {
    int L = 1;
    while ((1 << L) < a.size()) L++;
    while ((1 << L) < b.size()) L++;
    int n = 1 << (L+1);

    VC aa, bb;
    for (size_t i = 0; i < n; i++) aa.push_back(i < a.size() ? COMPLEX(a[i], 0) : 0);
    for (size_t i = 0; i < n; i++) bb.push_back(i < b.size() ? COMPLEX(b[i], 0) : 0);
    
    VC AA = DFT(aa, false);
    VC BB = DFT(bb, false);
    VC CC;
    for (size_t i = 0; i < AA.size(); i++) CC.push_back(AA[i] * BB[i]);
    VC cc = DFT(CC, true);

    VD c;
    for (int i = 0; i < a.size() + b.size() - 1; i++) c.push_back(cc[i].real());
    return c;
  }

};

int main()
{
    long long P = 200003;
  	long long p2[200002];
  
  	p2[0] = 1;
    for (int i = 0; i < 200002-1;i++){
    	p2[i + 1] = (p2[i] * 2) % P;
    }
  
 	int rev[200003];
  	for (int i = 0; i < 200002; i++){
    	rev[p2[i]] = i;
    }	
  
	VD a = VD (P);
  	long long sub = 0;
  	long long n,v;
  	cin >> n;
  	for (int i = 0; i < n; i++){
    	cin >> v;
      	sub += (v * v) % P;
      	if (v != 0){
          a[rev[v]] += 1;
        }
    }
  	FFT fft;
	VD b = fft.Convolution(a, a);
	long long out = 0;
	for (int i = 0; i < b.size(); i++){
      	long long val = (b[i] + 0.5);
      	//if (val){
        //	cout << i << " " << val << "\n"; 
        //}
		out += val * p2[i % (P - 1)];
    }
  	out -= sub;
  	out /= 2;
  	cout << out;
	return 0;
}
### Prompt

Please create a solution in CPP to 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
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

#include <iostream>
#include <vector>
#include <complex>

using namespace std;

typedef long double DOUBLE;
typedef complex<DOUBLE> COMPLEX;
typedef vector<DOUBLE> VD;
typedef vector<int> VI;
typedef vector<COMPLEX> VC;

struct FFT {
  VC A;
  int n, L;

  int ReverseBits(int k) {
    int ret = 0;
    for (int i = 0; i < L; i++) {
      ret = (ret << 1) | (k & 1);
      k >>= 1;
    }
    return ret;
  }

  void BitReverseCopy(VC a) {
    for (n = 1, L = 0; n < a.size(); n <<= 1, L++) ;
    A.resize(n);
    for (int k = 0; k < n; k++) 
      A[ReverseBits(k)] = a[k];
  }
  
  VC DFT(VC a, bool inverse) {
    BitReverseCopy(a);
    for (int s = 1; s <= L; s++) {
      int m = 1 << s;
      COMPLEX wm = exp(COMPLEX(0, 2.0 * M_PI / m));
      if (inverse) wm = COMPLEX(1, 0) / wm;
      for (int k = 0; k < n; k += m) {
	COMPLEX w = 1;
	for (int j = 0; j < m/2; j++) {
	  COMPLEX t = w * A[k + j + m/2];
	  COMPLEX u = A[k + j];
	  A[k + j] = u + t;
	  A[k + j + m/2] = u - t;
	  w = w * wm;
	}
      }
    }
    if (inverse) for (int i = 0; i < n; i++) A[i] /= n;
    return A;
  }

  // c[k] = sum_{i=0}^k a[i] b[k-i]
  VD Convolution(VD a, VD b) {
    int L = 1;
    while ((1 << L) < a.size()) L++;
    while ((1 << L) < b.size()) L++;
    int n = 1 << (L+1);

    VC aa, bb;
    for (size_t i = 0; i < n; i++) aa.push_back(i < a.size() ? COMPLEX(a[i], 0) : 0);
    for (size_t i = 0; i < n; i++) bb.push_back(i < b.size() ? COMPLEX(b[i], 0) : 0);
    
    VC AA = DFT(aa, false);
    VC BB = DFT(bb, false);
    VC CC;
    for (size_t i = 0; i < AA.size(); i++) CC.push_back(AA[i] * BB[i]);
    VC cc = DFT(CC, true);

    VD c;
    for (int i = 0; i < a.size() + b.size() - 1; i++) c.push_back(cc[i].real());
    return c;
  }

};

int main()
{
    long long P = 200003;
  	long long p2[200002];
  
  	p2[0] = 1;
    for (int i = 0; i < 200002-1;i++){
    	p2[i + 1] = (p2[i] * 2) % P;
    }
  
 	int rev[200003];
  	for (int i = 0; i < 200002; i++){
    	rev[p2[i]] = i;
    }	
  
	VD a = VD (P);
  	long long sub = 0;
  	long long n,v;
  	cin >> n;
  	for (int i = 0; i < n; i++){
    	cin >> v;
      	sub += (v * v) % P;
      	if (v != 0){
          a[rev[v]] += 1;
        }
    }
  	FFT fft;
	VD b = fft.Convolution(a, a);
	long long out = 0;
	for (int i = 0; i < b.size(); i++){
      	long long val = (b[i] + 0.5);
      	//if (val){
        //	cout << i << " " << val << "\n"; 
        //}
		out += val * p2[i % (P - 1)];
    }
  	out -= sub;
  	out /= 2;
  	cout << out;
	return 0;
}
```