program calcul;
const zero=ord('0');
      zece=ord('A');
var i,n,lb,nr,j:longint;
    aa,ab,s,baza:int64;
    c:byte;
    f:text;
    a:array[1..100010]of char;
    b:array[1..50000]of char;
    pow:array[0..3]of byte;
begin
assign(f,'calcul.in');reset(f);
n:=0;
while not seekeoln(f) do begin
      inc(n);
      read(f,a[n]);
end;
readln(f);
lb:=0;
while not seekeoln(f) do begin
      inc(lb);
      read(f,b[lb]);
end;
readln(f);
read(f,c);
close(f);
baza:=1;
if c>n then begin
                for i:=1 to c-n do
                        begin
                        a[i+n]:=a[i];
                        a[i]:='0';
                        end;
                n:=c;
            end;

for i:=c-1 downto 0 do begin
    ab:=ab*10+ord(a[n-i])-zero;
    baza:=baza*10;
end;
aa:=ab;
ab:=1;
pow[0]:=1;
pow[1]:=2;
pow[2]:=4;
pow[3]:=8;
case b[1] of
     '0'..'9':nr:=ord(b[1])-zero;
     'A'..'F':nr:=ord(b[1])-zece+10;
end;
i:=3;
while nr xor pow[i]>nr do dec(i);
    for j:=i downto 0 do
    begin
            s:=s*(1+ab);
            ab:=ab*ab;
            ab:=ab mod baza;
            {while ab>=baza do
                  dec(ab,baza);}
    if nr xor pow[j]<nr then begin
                        s:=((s+1)*aa);
                        ab:=ab*aa;
                        end;
    {while s>=baza do
          dec(s,baza);}
    s:=s mod baza;
    end;

for i:=2 to lb do begin
    case b[i] of
         '0'..'9':nr:=ord(b[i])-zero;
         'A'..'F':nr:=ord(b[i])-zece+10;
    end;

    for j:=3 downto 0 do
    begin
            s:=s*(1+ab);
            ab:=ab*ab;
            ab:=ab mod baza;
            {while ab>=baza do
                  dec(ab,baza);}
    if nr xor pow[j]<nr then begin
                        s:=((s+1)*aa);
                        ab:=ab*aa;
                        end;
    {while s>=baza do
          dec(s,baza);}
    s:=s mod baza;
    end;
end;
assign(f,'calcul.out');rewrite(f);
while s<baza do begin
      write(f,0);
      baza:=baza div 10;
end;
if s<>0 then write(f,s);
close(f);
end.