program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int64):: n,x,m
    integer(int64):: i
    integer(int64):: c, l_len, l_num, end_len
    integer(int64):: v_loop, v_non_loop
    integer(int64), allocatable:: v(:), v_sum(:), ind(:)


    read*, n,x,m
    allocate(v, source=[(merge(x,0_8,i==1),i=1,m)])
    allocate(v_sum(0:m), source=[0_8,v])
    allocate(ind(0:m), source=[(merge(1_8,0_8,i==x),i=0,m)])

    do i=2,m+1
        v(i)=mod(v(i-1)*v(i-1),m)
        v_sum(i)=v_sum(i-1)+v(i)
        if (i==n) then
            print'(i0)', v_sum(i)
            stop
        end if

        if (ind(v(i)) == 0) then
            ind(v(i))=i
        else
            c = ind(v(i))-1
            l_len = i-ind(v(i))
            l_num = (n-c)/l_len
            end_len = mod((n-c),l_len)

            v_loop = (v_sum(c+l_len)-v_sum(c))*l_num
            v_non_loop = v_sum(c+end_len)
            print'(i0)', v_loop+v_non_loop
            stop
        end if
    end do
end program main