N,X,M = gets.chomp.split.map(&:to_i)
an = X
ans = 0
s = 0
ss = 0
count = 0
countcount = 0
kokomade = 0
kokomademade = 0
ppp = 0

if X == 1
  puts N
  exit
end

(1..N).each do |i|
  if i == 1
  	anan = an % M
  else
  	anan = (an**2 % M)
    if anan == 0
      puts ans
      exit
    elsif anan == s
      ans += (ans - kokomade) * ((N - i + 1) / (i - count))
      add = ((N - i + 1) % (i - count))
      (1..add).each do |j|
        ans += anan
        ananan = anan**2 % M
        anan = ananan
      end
      puts ans
      exit
    elsif anan == ss
      ans += (ans - kokomademade) * ((N - i + 1) / (i - countcount))
      add = ((N - i + 1) % (i - countcount))
      (1..add).each do |j|
        ans += anan
        ananan = anan**2 % M
        anan = ananan
      end
      puts ans
      exit
    end
  end
  if an**2 > M && ppp == 0
    s = anan
    kokomade = ans
    count = i
    ppp += 1
  end
  if i > 20 && ppp == 1
    ss = anan
    kokomademade = ans
    countcount = i
    ppp += 1
  end
  ans += anan
  an = anan
end

puts ans