program fa;
var
  r:longint;
  i,j,k,n:longint;
function c(a,b:longint):longint;
var
  i1,q:longint;
begin
if (b=0)or(a=b)
  then begin
    c:=1;
    exit;
  end;
q:=1;
  for i1:=a downto a-b+1 do
    begin
      q:=q*i1 div (a-i1+1);
    end;
  c:=q;
end;
begin
  r:=0;
  read(n);
  read(k);
  for i:=0 to n div 2 do
    begin
      r:=r+(c(n-i,i))*trunc(exp((n-i)*ln(k-1)));
    end;
    writeln(r);
end.

Use long arithmetic and algorithm 1009 :)))