program sequence_sum
  implicit none
  integer(8) :: n, x, m, a(100000) = -1, num
  integer :: i, b(0:100000) = -1, period, offset, rem
  read(*,*) n, x, m
  if (n <= 200000) then
    num = x
    do i = 2, int(n)
      x = mod(x * x, m)
      if (x == 0) exit
      num = num + x
    end do
    write(*,'(i0)') num
    stop
  end if
  a(1) = x
  b(int(a(1))) = 1
  do i = 2, int(m) + 1
    x = mod(x * x, m)
    a(i) = x
    if (b(int(x)) > 0) then
      offset = b(int(x)) - 1
      period = i - b(int(x))
      exit
    end if
    b(int(x)) = i
  end do
  num = (n - offset) / period
  rem = int(n - offset - num * period)
  write(*,'(i0)') sum(a(1:offset)) + sum(a(offset + 1:offset + period)) * num + &
    sum(a(offset + 1:offset + rem))
end program sequence_sum