module mod_ntt
  implicit none
  integer, parameter :: intkind = 16
  integer(intkind), parameter :: modu = 7881299347898369_intkind, root = 3_intkind
contains
  function convolve(a, na, b, nb) result(res)
    integer, intent(in) :: na, nb
    integer(intkind), intent(in) :: a(0:na), b(0:nb)
    integer(intkind), allocatable :: fa(:), fb(:), f(:)
    integer(intkind) :: res(0:na + nb)
    integer :: p
    p = find_pow2(na + nb + 1)
    allocate(fa(0:p - 1), fb(0:p - 1), f(0:p - 1))
    call init(a, na, fa, p)
    call ntt(fa, p)
    call init(b, nb, fb, p)
    call ntt(fb, p)
    f = mod(fa * fb, modu)
    call ntt(f, p, .true.)
    res = f(0:na + nb)
  end
  integer function find_pow2(n) result(res)
    integer, intent(in) :: n
    res = n - 1
    res = or(res, rshift(res, 1))
    res = or(res, rshift(res, 2))
    res = or(res, rshift(res, 4))
    res = or(res, rshift(res, 8))
    res = or(res, rshift(res, 16))
    res = res + 1
  end
  subroutine init(a, n, f, p)
    integer, intent(in) :: n, p
    integer(intkind), intent(in) :: a(0:n)
    integer(intkind), intent(out) :: f(0:p - 1)
    f(0:n) = a(0:n)
    f(n + 1:p - 1) = 0
  end
  subroutine ntt(f, p, invert)
    integer, intent(in) :: p
    integer(intkind), intent(inout) :: f(0:p - 1)
    logical, optional, intent(in) :: invert
    integer(intkind) :: w, z, pz, x, y
    integer :: i, j, r, m
    logical :: inverse
    inverse = merge(invert, .false., present(invert))
    w = pow(root, (modu - 1) / p)
    if (inverse) w = inv(w)
    r = 0
    do i = 1, p - 2
      j = p / 2
      do
        r = xor(r, j)
        if (j <= r) exit
        j = j / 2
      end do
      if (i < r) call swap(f(i), f(r))
    end do
    m = 1
    do while (m < p)
      pz = 1
      z = pow(w, int(p / (2 * m), intkind))
      do i = 0, m - 1
        do j = i, p - 1, 2 * m
          x = f(j)
          y = mod(f(j + m) * pz, modu)
          f(j) = mod(x + y, modu)
          f(j + m) = modulo(x - y, modu)
        end do
        pz = mod(pz * z, modu)
      end do
      m = m * 2
    end do
    if (inverse) f = mod(f * inv(int(p, intkind)), modu)
  end
  integer(intkind) function pow(a, b) result(res)
    integer(intkind), intent(in) :: a, b
    integer(intkind) :: r, p
    res = 1
    r = b
    p = a
    do while (r > 0)
      if (btest(r, 0)) res = mod(res * p, modu)
      p = mod(p * p, modu)
      r = rshift(r, 1)
    end do
  end
  integer(intkind) function inv(a) result(res)
    integer(intkind), intent(in) :: a
    res = pow(a, modu - 2)
  end
  subroutine swap(a, b)
    integer(intkind), intent(inout) :: a, b
    a = xor(a, b)
    b = xor(a, b)
    a = xor(a, b)
  end
end module mod_ntt
program product_modulo
  use mod_ntt
  implicit none
  integer, parameter :: p = 200003, h = 100002
  integer :: n, i, q = 1, a(0:200000) = 0, map(0:p - 1) = 0
  integer(intkind) :: x = 0, cnt(0:2 * p - 2) = 0
  read(*,*) n
  read(*,*) a(1:n)
  do i = 0, p - 1
    map(q) = i
    q = merge(q + q, q + q - p, q < h)
  end do
  do i = 1, n
    if (a(i) == 0) cycle
    x = x - mod(int(a(i), intkind) * a(i), int(p, intkind))
    cnt(map(a(i))) = cnt(map(a(i))) + 1
  end do
  cnt(0:2 * p - 2) = convolve(cnt(0:p - 1), p - 1, cnt(0:p - 1), p - 1)
  q = 1
  do i = 0, 2 * p - 2
    x = x + cnt(i) * q
    q = merge(q + q, q + q - p, q < h)
  end do
  write(*,'(i0)') x / 2
end program product_modulo

Measured memory_bytes: 38592