Scanf.scanf "%d %d %d" (fun n x m ->
    let a = Array.make (m + 2) 0 in
    let flag = Array.make (m + 2) (-1) in
    a.(0) <- x;
    flag.(x) <- 0;
    let rec loop i prev =
        let c = (prev * prev) mod m in
        if flag.(c) >= 0 then flag.(c), i else (
            a.(i) <- c;
            flag.(c) <- i;
            loop (i + 1) c
        )
    in
    let pre, j = loop 1 x in
    let len = j - pre in

    Printf.printf "%d\n" @@
        if n <= j then (
            let rec loop i acc =
                if i = n then acc else
                    loop (i + 1) (acc + a.(i))
            in
            loop 0 0
        ) else (
            let presum =
                let rec loop i acc =
                    if i = pre then acc else
                        loop (i + 1) (acc + a.(i))
                in
                loop 0 0
            in
            let loopsum =
                let rec loop i acc =
                    if i = j then acc else
                        loop (i + 1) (acc + a.(i))
                in
                loop pre 0
            in
            let postsum =
                let lim = ((n - pre) mod len) + pre in
                let rec loop i acc =
                    if i = lim then acc else
                        loop (i + 1) (acc + a.(i))
                in
                loop pre 0
            in
            presum + loopsum * ((n - pre) / len) + postsum
        )
)