var n,p:int64;

const mare=1999999973;

procedure citire;
        var f:text;
        begin
        assign(f,'lgput.in');
         reset(f);
         readln(f,n,p);
         close(f);
        end;

procedure scrie(k:int64);
        var f:text;
        begin
        assign(f,'lgput.out');
         rewrite(f);
         writeln(f,k);
         close(f);
        end;

function put(x,k,n:int64):int64;
        var a,b:int64;
        begin
        if k=0 then
           put:=1
        else
           if k mod 2 =0 then begin
              a:=put(x, k div 2, n);
              put:=a*a mod n
           end else begin
              a:=put(x, k div 2, n);
              b:=(a*a) mod n;
              put:=b*x mod n;
              end;
        end;

begin
citire;
scrie(put(n,p,mare));
end.