#!/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

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 = [
    [int(A % MOD), 1],
    [0, 1]
]

rez = [
    [1, 0],
    [0, 1],
]

B += 1
while B:
    if B % 2:
        rez = matrix_mul(rez, mat)
    mat = matrix_mul(mat, mat)
    B /= 2

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