output_description: Print one integer — the sum over ((A_i \cdot A_j) \bmod P).
  
  * * *
input_description: Input is given from Standard Input in the following format.
  
      
      
      N
      A_1 A_2 \cdots A_N
attempt: def convolve(A, B):
      # 畳み込み  # 要素は整数
      # 3 つ以上の場合は一度にやった方がいい
      import numpy as np
  
      dtype = np.int64  # np.float128 は windows では動かない？
      fft, ifft = np.fft.rfft, np.fft.irfft
      a, b = len(A), len(B)
      if a == b == 1:
          return np.array([A[0] * B[0]])
      n = a + b - 1  # 返り値のリストの長さ
      k = 1 << (n - 1).bit_length()  # n 以上の最小の 2 冪
      AB = np.zeros((2, k), dtype=dtype)
      AB[0, :a] = A
      AB[1, :b] = B
      return np.rint(ifft(fft(AB[0]) * fft(AB[1]))).astype(np.int64)[:n]
  
  
  import sys
  import numpy as np
  
  input = sys.stdin.readline
  
  P = 200003
  N = int(input())
  A = sorted(map(int, input().split()))
  A = [a for a in A if a]
  Bucket = [0] * P
  for a in A:
      Bucket[a] += 1
  
  Perm = []
  Perm_inv = [0] * (P)
  p = 1
  for i in range(P):
      Perm.append(p)
      p = p * 2 % P
  for i, p in enumerate(Perm):
      Perm_inv[p] = i
  #
  # print(Perm[:9])
  # print(Perm_inv[:9])
  
  
  def perm(arr, P):
      res = [0] * len(arr)
      for a, p in zip(arr, P):
          res[p] = a
      return res
  
  
  B = perm(Bucket, Perm_inv)
  C = convolve(B, B)
  C_ = C[:P].copy()
  C_[: len(C) - P + 1] += C[P - 1 :]
  C_ = perm(C_, Perm)
  # for i, c in enumerate(C_):
  #     if c:
  #         print(i%P)
  Ans = C_ * np.arange(P)
  an = Ans.sum()
  diag = sum(a * a % P for a in A)
  
  ans = (an - diag) // 2
  print(ans)
  
problem_description: Statement
  
  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.
samples: [{"input": "4\n    2019 0 2020 200002", "output": "474287\n    \n\nThe non-zero products are:\n\n  * 2019 \\cdot 2020 \\bmod P = 78320\n  * 2019 \\cdot 200002 \\bmod P = 197984\n  * 2020 \\cdot 200002 \\bmod P = 197983\n\nSo the answer is 0 + 78320 + 197984 + 0 + 0 + 197983 = 474287.\n\n* * *"}, {"input": "5\n    1 1 2 2 100000", "output": "600013"}]