def f(x, m):

    return (x ** 2) % m





def main():

    n, x, m = list(map(int, input().split()))

    lst = [[False, 0] for _ in range((m + 1))]

    lst[x] = [True, 1]

    res = [x]

    loop = 0



    for i in range(2, m + 1):

        x = f(x, m)

        if lst[x][0] == False:

            lst[x][0] = True

            lst[x][1] = i

            res.append(x)

        else:

            loop = i - lst[x][1]

            non_loop = lst[x][1] - 1

            break

    if loop == 0:

        print((sum(res[:n])))

        exit()

    ans = sum(res[:non_loop])

    ans += (n - non_loop) // loop * sum(res[non_loop:])

    ans += sum(res[non_loop:non_loop + (n - non_loop) % loop])

    print(ans)





if __name__ == "__main__":

    main()

def main():

    n, x, m = list(map(int, input().split()))

    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか

    res = []  # 数列A



    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する

        if idx[x] == -1:  # 初めて

            idx[x] = i

            res.append(x)

        else:  # 既出（ループ発見）

            len_loop = i - idx[x]

            len_head = idx[x] - 1

            break

        x = (x ** 2) % m



    if n <= len_head + len_loop:  # 1ループ目までで出力する場合

        print((sum(res[:n])))

    else:

        ans = sum(res[:len_head])  # ループ前

        ans += (n - len_head) // len_loop * sum(res[len_head:])  # ループ

        ans += sum(res[len_head: len_head + (n - len_head) %

                       len_loop])  # ループ後の余り

        print(ans)





if __name__ == "__main__":

    main()

def f(x, m):
    return (x**2) % m


def main():
    n, x, m = list(map(int, input().split()))
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]
    loop = 0
    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break
    if loop == 0:
        print((sum(res[:n])))
        exit()
    ans = sum(res[:non_loop])
    ans += (n - non_loop) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop : non_loop + (n - non_loop) % loop])
    print(ans)


if __name__ == "__main__":
    main()

def main():
    n, x, m = list(map(int, input().split()))
    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか
    res = []  # 数列A
    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する
        if idx[x] == -1:  # 初めて
            idx[x] = i
            res.append(x)
        else:  # 既出（ループ発見）
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break
        x = (x**2) % m
    if n <= len_head + len_loop:  # 1ループ目までで出力する場合
        print((sum(res[:n])))
    else:
        ans = sum(res[:len_head])  # ループ前
        ans += (n - len_head) // len_loop * sum(res[len_head:])  # ループ
        ans += sum(res[len_head : len_head + (n - len_head) % len_loop])  # ループ後の余り
        print(ans)


if __name__ == "__main__":
    main()

-def f(x, m): -    return (x**2) % m - - -    lst = [[False, 0] for _ in range((m + 1))] -    lst[x] = [True, 1] -    res = [x] -    loop = 0 -    for i in range(2, m + 1): -        x = f(x, m) -        if lst[x][0] == False: -            lst[x][0] = True -            lst[x][1] = i +    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか +    res = []  # 数列A +    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する +        if idx[x] == -1:  # 初めて +            idx[x] = i -        else: -            loop = i - lst[x][1] -            non_loop = lst[x][1] - 1 +        else:  # 既出（ループ発見） +            len_loop = i - idx[x] +            len_head = idx[x] - 1 -    if loop == 0: +        x = (x**2) % m +    if n <= len_head + len_loop:  # 1ループ目までで出力する場合 -        exit() -    ans = sum(res[:non_loop]) -    ans += (n - non_loop) // loop * sum(res[non_loop:]) -    ans += sum(res[non_loop : non_loop + (n - non_loop) % loop]) -    print(ans) +    else: +        ans = sum(res[:len_head])  # ループ前 +        ans += (n - len_head) // len_loop * sum(res[len_head:])  # ループ +        ans += sum(res[len_head : len_head + (n - len_head) % len_loop])  # ループ後の余り +        print(ans)