Program Calcul;

var A,C,i,k,n,o,j: longint;
    B:char;
    f,g:text;

function zece(y:integer):longint;

begin
zece:=1;
for i:=1 to y do
    zece:=zece*10;
end;

function putere(x,n:integer):longint;
var s:longint;
    p:longint;
begin
s:=0;
p:=x;
k:=zece(C);
for i:=1 to n do
    begin
    p:=p mod k;
    s:=s+p;
    p:=p*x;
    end;

putere:=s;
end;


begin
assign(f,'calcul.in'); reset(f);
assign(g,'calcul.out'); rewrite(g);

readln(f,A);
readln(f,B);
readln(f,C);

case B of
        '1': o:=1;
        '2': o:=2;
        '3': o:=3;
        '4': o:=4;
        '5': o:=5;
        '6': o:=6;
        '7': o:=7;
        '8': o:=8;
        '9': o:=9;
        'A': o:=10;
        'B': o:=11;
        'C': o:=12;
        'D': o:=14;
        'E': o:=15;
        'F': o:=16;
        end;

writeln(g,putere(A,o) mod k);

close(f);
close(g);
end.