program ff;
  var
    n,i,j,k,l,t:integer;
    u0,u1,u2,a,b,c:array[0..2000] of byte;

  function max(a,b:integer):integer;
    begin
      if a>b then max:=a else max:=b;
    end;

  procedure sum(a,b:array of byte);
    begin
      l:=max(a[0],b[0]);
      fillchar(c,sizeof(c),0);
      t:=0;
      for i:=1 to l do begin
        c[i]:=(a[i]+b[i]+t) mod 10;
        t:=(a[i]+b[i]+t) div 10;
      end;
      c[0]:=l;
      if t<>0 then begin
        c[0]:=l+1;
        c[l+1]:=t;
      end;
    end;

  procedure mult(a:array of byte);
    begin
      l:=k-1;
      t:=0;
      fillchar(c,sizeof(c),0);
      for i:=1 to a[0] do begin
        c[i]:=(l*a[i]+t) mod 10;
        t:=(l*a[i]+t) div 10;
      end;
      c[0]:=a[0];
      if t<>0 then begin
        c[0]:=a[0]+1;
        c[c[0]]:=t;
      end;
    end;

  procedure solve;
    begin
      u0[1]:=1; u0[0]:=1;
      u1[1]:=k-1; u1[0]:=1;
      for j:=2 to n do begin
        sum(u0,u1);
        u2:=c;
        mult(u2);
        u2:=c;
        u0:=u1;
        u1:=u2;
      end;
    end;

  begin
    readln(n,k);
    solve;
    for i:=u2[0] downto 1 do write(u2[i]);
    writeln;
  end.

> program ff;
>   var
>     n,i,j,k,l,t:integer;
>     u0,u1,u2,a,b,c:array[0..2000] of byte;
>
>   function max(a,b:integer):integer;
>     begin
>       if a>b then max:=a else max:=b;
>     end;
>
>   procedure sum(a,b:array of byte);
>     begin
>       l:=max(a[0],b[0]);
>       fillchar(c,sizeof(c),0);
>       t:=0;
>       for i:=1 to l do begin
>         c[i]:=(a[i]+b[i]+t) mod 10;
>         t:=(a[i]+b[i]+t) div 10;
>       end;
>       c[0]:=l;
>       if t<>0 then begin
>         c[0]:=l+1;
>         c[l+1]:=t;
>       end;
>     end;
>
>   procedure mult(a:array of byte);
>     begin
>       l:=k-1;
>       t:=0;
>       fillchar(c,sizeof(c),0);
>       for i:=1 to a[0] do begin
>         c[i]:=(l*a[i]+t) mod 10;
>         t:=(l*a[i]+t) div 10;
>       end;
>       c[0]:=a[0];
>       if t<>0 then begin
>         c[0]:=a[0]+1;
>         c[c[0]]:=t;
>       end;
>     end;
>
>   procedure solve;
>     begin
>       u0[1]:=1; u0[0]:=1;
>       u1[1]:=k-1; u1[0]:=1;
>       for j:=2 to n do begin
>         sum(u0,u1);
>         u2:=c;
>         mult(u2);
>         u2:=c;
>         u0:=u1;
>         u1:=u2;
>       end;
>     end;
>
>   begin
>     readln(n,k);
>     solve;
>     for i:=u2[0] downto 1 do write(u2[i]);
>     writeln;
>   end.
>
>
>

>