//By BLADEVIL

const

    d39                         =;

type

    rec                         =array[..,..] of int64;

var

    n, m                        :int64;

    p                           :int64;

    ans, sum                    :rec;

    w                           :int64;

function mul(a,b:rec):rec;

var

    i, j, k                     :longint;

begin

    fillchar(mul,sizeof(mul),);

    for i:= to  do

        for j:= to  do

            for k:= to  do mul[i,j]:=mul[i,j]+(a[i,k]*b[k,j]) mod d39;

end;

begin

    read(m,n);

    if n= then

    begin

        writeln();

        halt;

    end;

    ans[,]:=; ans[,]:=;

    sum[,]:=m-; sum[,]:=; sum[,]:=m;

    p:=n-;

    while p<> do

    begin

        if p mod = then ans:=mul(ans,sum);

        p:=p div ;

        sum:=mul(sum,sum);

    end;

    w:=((ans[,]*((m*m-m) mod d39) mod d39)+(ans[,]*m mod d39))mod d39;

    writeln(w);

end.