a = gets.split(" ")
$n = a[0].to_i
$x = a[1].to_i
$m = a[2].to_i

if $n < 10**6 
  ans = 0
  a = $x
  $n.times do |i|
    ans += a 
    a = (a * a) % $m
  end
  puts ans
else
  cycle = [$x]
  cycle_sum = $x
  s1 = Hash.new
  s1[$x] = 0

  element = $x
  $first_in_cycle = 0
  $m.times do |i|
    element = (element * element) % $m 
    if (s1.include?(element))
      $first_in_cycle = s1[element]
      $first_in_cycle.times do |j|
        cycle_sum -= cycle[j]
      end
      break
    end
    cycle.push(element)
    cycle_sum += element
    s1[element] = i+1
  end
  # byebug
  q = ($n - $first_in_cycle) / (cycle.length - $first_in_cycle)
  r = ($n - $first_in_cycle) % (cycle.length - $first_in_cycle)
  ans = q * cycle_sum
  r.times do |i|
    ans += cycle[$first_in_cycle + i]
  end
  $first_in_cycle.times do |i|
    ans += cycle[i]
  end
  puts ans
end
