program puteri;
type numar=array[0..100{!!!}] of longint;
var f, g:text;
    rez, vx:numar;
    x, n, i:longint;
    r:int64;

function prod(a,b:numar):numar;
var c:numar;
    i, k, t, j:longint;
  begin
    for i:=0 to 100{!!!} do
      c[i]:=0;
    for i:=1 to a[0] do
      for j:=1 to b[0] do
        c[i+j-1]:=c[i+j-1]+a[i]*b[j];
    t:=0;
    c[0]:=a[0]+b[0]-1;
    for i:=1 to c[0] do
      begin
        k:=c[i]+t;
        c[i]:=k mod 10;
        t:=k div 10;
      end;
    if t>0 then
      begin
        c[0]:=c[0]+1;
        c[c[0]]:=t;
      end;
    prod:=c;
  end;

function gen(k:longint):numar;
var nr:numar;
  begin
    if k=0 then
      begin
        gen[0]:=1;
        gen[1]:=1;
      end
     else
       if k mod 2=0 then
         begin
           nr:=gen(k div 2);
           gen:=prod(nr,nr);
         end
        else
          begin
            nr:=gen(k-1);
            gen:=prod(nr,vx);
          end;
  end;

  begin
    assign(f,'lgput.in'); reset(f);
    assign(g,'lgput.out'); rewrite(g);
    read(f,x);
    while x>0 do
      begin
        vx[0]:=vx[0]+1;
        vx[vx[0]]:=x mod 10;
        x:=x div 10;
      end;
    readln(f,n);
    rez:=gen(n);
    r:=0;
    for i:=rez[0] downto 1 do
      begin
        r:=(r*10+rez[i]) mod 1999999973;
{        write(g,rez[i]);}
      end;
    writeln(g,r);
    close(f);
    close(g);
  end.