Perevod

program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };

var
  inp,outp: text;
  x,y,aL,bL,i: longint;
  q,p,pplength,r,promL,cur: byte;
  a: array[0..1000] of longint;
  pPreob,prom: array[0..10] of byte;
  b,b1: array[0..10000] of longint;
  flag1: boolean;
  k: char;

procedure CountBL;
begin
 bL:=10000;
 while b[bL]=0 do dec(bL);
end;

procedure Preob(x: byte);
var
  y: byte;
begin
 y:=1;
 while x>q do begin
  prom[y]:=x mod q;
  x:=x div q;
  inc(y);
 end;
 prom[y]:=x;
 promL:=y;
end;

begin
 assignfile(inp,'input.txt');
 assignfile(outp,'output.txt');
 rewrite(outp);
 reset(inp);
 //Reading inp
 readln(inp,p,q);
 aL:=0;
 repeat
   inc(aL);
   read(inp,k);
   a[aL]:=ord(k)-48;
   if a[aL]>10 then a[aL]-=7;
 until EOLn(inp);
 //Counting pPreob=(p)q and pplength
 x:=p;
 y:=1;
 while x>q do begin
  pPreob[y]:=x mod q;
  x:=x div q;
  inc(y);
 end;
 pPreob[y]:=x;
 pplength:=y;
 for y:=1 to pplength do write(pPreob[y]);   //
 writeln;                                    //
 //Clear b[]
 for x:=0 to 10000 do b[x]:=0;
 //Main cycle
 if (aL>1) then for x:=1 to (aL-1) do begin
  Preob(a[x]);
  r:=0;
  for y:=1 to promL do begin
   b[y]:=b[y]+r+prom[y];
   r:=b[y] div q;
   b[y]:=b[y] mod q;
  end;
  b[promL+1]+=r;
  //X pPreob
  CountBL;
  for i:=bL downto 1 do
  for y:=1 to bL do b1[y]:=b[y];
  for y:=1 to bL do b[y]:=0;
  for y:=1 to pplength do begin
   r:=0;
   for i:=1 to bL do begin
    cur:=y+i-1;
    b[cur]+=b1[i]*pPreob[y]+r;
    r:=b[cur] div q;
    b[cur]:=b[cur] mod q;
   end;
   b[cur+1]:=r;
  end;
 end;
 //Adding the last one
 Preob(a[x]);
 r:=0;
 for y:=1 to promL do begin
  b[y]:=b[y]+r+prom[y];
  r:=b[y] div q;
  b[y]:=b[y] mod q;
 end;
 b[promL+1]+=r;
 //Writing outp
 CountBL;
 for x:=bL downto 1 do begin
  if b[x]>9 then write(outp,chr(b[x]+55)) else
    write(outp,chr(b[x]+48));
 end;
 closefile(outp);
 closefile(inp);
 readln;         //
end.