import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.sqrt

fun main(args: Array<String>) {

    // IO Templates
    val br = BufferedReader(InputStreamReader(System.`in`))
    val out = PrintWriter(System.out)

    val (n, originX, m) = br.readLine()!!.split(' ').map { it.toLong() }

    var x = originX

    if (n == 1L) {
        println(x)
        return
    }

    val s = mutableSetOf(x)

    var loopRoot = 0L
    var loopEndAt = 0L
    var initialSum = 0L

    for (i in 1..n) {
        initialSum += x
        if(i == n) break
        x = x * x % m
        if (s.contains(x)) {
            loopRoot = x
            loopEndAt = i + 1
            break
        }
        s.add(x)
    }

    if(loopEndAt == 0L){
        println(initialSum)
        return
    }

    x = originX
    var loopStartAt = 0L
    var sumTillLoop = 0L
    for (i in 1..n) {
        if (x == loopRoot) {
            loopStartAt = i
            break
        }
        sumTillLoop += x
        x = x * x % m
    }

    val loopLength = loopEndAt - loopStartAt
    var oneLoopSum = 0L

    x = loopRoot

    for (i in 0..loopLength) {
        x = x * x % m
        oneLoopSum += x
        if (x == loopRoot) {
            break
        }
    }

    var ans = sumTillLoop + ((n - loopStartAt + 1) / loopLength) * oneLoopSum

    x = loopRoot

    for (i in 0 until (n - loopStartAt + 1) % loopLength) {
        ans += x
        x = x * x % m
    }

    out.println(ans)

    out.flush()
}