object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextLong()
  val x, m = sc.nextInt()

  val a = Array.fill(m)(0L)
  val idx = Array.fill(m)(-1)

  var i = 0
  var now = x.toLong
  while (idx(now.toInt) == -1) {
    idx(now.toInt) = i
    a(i) = now
    now = (now * now) % m
    i += 1
  }

  val s = idx(now.toInt)
  val e = i - 1
  val l = e - s + 1
  val ac = a.scanLeft(0L)(_+_)
  var ans = 0L

  var r = n
  ans += ac(s)
  r -= s

  ans += (ac(e+1) - ac(s)) * (r / l)
  ans += ac(s + (r % l).toInt) - ac(s)

  println(ans)
}
