const   modulo=10000000000;
        modulo1=1999999973;
var     a,c:int64;
        n,nr,k,p:longint;
        f1,f2:text;

function produs(p:longint):longint;
var l:longint;
begin
  l:=1;
  a:=nr;
  while l*2<=p do
    begin
      l:=l*2;
      a:=(a*a) mod modulo;
    end;
  produs:=l;
end;


begin
  assign(f1,'lgput.in');
  assign(f2,'lgput.out');
  reset(f1);
  rewrite(f2);
  readln(f1,nr,n);
  if n=0 then write(f2,1) else
  begin
  p:=produs(n);
  c:=a;
  while p<n do
    begin
      k:=produs(n-p);
      c:=(c*a) mod modulo;
      p:=p+k;
    end;
  writeln(f2,c mod modulo1);
  end;
  close(f2);
end.