use std::fs::File;
use std::io::{BufRead, BufReader, Write};

fn mod_pow(mut base: u64, mut exp: u64, modulo: u64) -> u64 {
    let mut result = 1;
    base %= modulo;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modulo;
        }
        base = base * base % modulo;
        exp /= 2;
    }
    result
}

fn main() {
    let fin = File::open("calcul.in").unwrap();
    let mut reader = BufReader::new(fin);
    let mut line = String::new();

    // A ca string
    reader.read_line(&mut line).unwrap();
    let a_str = line.trim().to_string();
    line.clear();

    reader.read_line(&mut line).unwrap();
    let b_str = line.trim().to_string();
    line.clear();

    reader.read_line(&mut line).unwrap();
    let c: u32 = line.trim().parse().unwrap();
    let modulo = 10u64.pow(c);

    // 1. Obținem A mod 10^C
    let mut a_mod = 0u64;
    for ch in a_str.chars() {
        if let Some(d) = ch.to_digit(10) {
            a_mod = (a_mod * 10 + d as u64) % modulo;
        }
    }

    // 2. Convertim B din hex
    let b: u64 = u64::from_str_radix(&b_str, 16).unwrap();

    // 3. Calculăm suma
    let mut sum = 0u64;
    for i in 1..=b {
        sum = (sum + mod_pow(a_mod, i, modulo)) % modulo;
    }

    // 4. Scriem outputul
    let mut fout = File::create("calcul.out").unwrap();
    write!(fout, "{:0>width$}", sum, width = c as usize).unwrap();
}