program Z3;

{$APPTYPE CONSOLE}
{$LONGSTRINGS ON}
uses
   SysUtils;

var
   m, k, i, j, index: Byte;
   DemicalNumber, Step, Temp, Num: Int64;
   EndNumber, ArrOfChar, Number: String ;
   Numeras: Boolean;
begin
   EndNumber := '';
   ArrOfChar := 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
   Readln(m, k);
   Readln(Number);
   if m <> 10 then
   begin
      DemicalNumber := 0;
      Step := 1;
      Numeras := True;
      for i := 1 to Length(Number) do
         if Number[i] in ['A'..'Z'] then
            Numeras := False;
      if Numeras then
      begin
         Num := StrToInt(Number);
         while Num <> 0 do
         begin
            Temp := Num mod 10;
            Num := Num div 10;
            DemicalNumber := DemicalNumber + Temp * Step;
            Step := Step * m;
         end;
      end
      else
      begin
            for i := Length(Number) downto 1 do
            begin
               Numeras := True;
               for j := 1 to Length(ArrOfChar) do
               begin
                  if Number[i] = ArrOfChar[j] then
                  begin
                     Numeras := False;
                     index := j;
                  end;
               end;
               if not Numeras then
                  Temp := index + 9
               else
                  Temp := StrToInt(Number[i]);
               DemicalNumber := DemicalNumber + Temp * Step;
               Step := Step*m;
            end;
      end;
   end
   else
   begin
      Num := StrToInt(Number);
      DemicalNumber := Num;
   end;
   if k = 10 then
      EndNumber := IntToStr(DemicalNumber)
   else
   begin
      while DemicalNumber > k do
      begin
         Temp := DemicalNumber mod k;
         if Temp >= 10 then
            EndNumber := ArrOfChar[Temp - 9] + EndNumber
         else
            EndNumber := IntToStr(Temp) + EndNumber;
         DemicalNumber := DemicalNumber div k;
      end;
      if DemicalNumber >= 10 then
         EndNumber := ArrOfChar[DemicalNumber - 9] + EndNumber
      else
         EndNumber := IntToStr(DemicalNumber) + EndNumber;
   end;
   Writeln(EndNumber);
   Readln;
end.