#!/usr/bin/env python

def matrix_mul(A, B):
    C = [[0, 0] for i in range(0, 2)]
    for i in range(0, 2):
        for j in range(0, 2):
            for k in range(0, 2):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def power(mat, pow):
    if pow == 0:
        return [
            [1, 0],
            [0, 1]
        ]

    if pow % 2:
        return matrix_mul(power(mat, pow - 1), mat)
    else:
        rez = power(mat, pow / 2)
        return matrix_mul(rez, rez)

f = open("calcul.in", "rt")
A = long(f.readline().strip())
B = long(f.readline().strip(), 16)
C = int(f.readline().strip())
MOD = 10 ** C

mat = [
    [A % MOD, 1],
    [0, 1]
]

rez = power(mat, B + 1)

open("calcul.out", "wt").write(("%%0%sd" % C) % (rez[0][1] - 1))