来自"NOCOW"

递推+高精=AC！

type bt=array[0..10000]of longint;

var f:array[0..2]of bt;

   s:bt;
   n,k,i:longint;

procedure add(a,b:bt;var c:bt); var i,x:longint; begin

   i:=1;
   x:=0;
   while (i<=a[0]) or(i<=b[0]) do begin
   x:=a[i]+b[i]+x div 10;
   c[i]:=x mod 10;
   inc(i);
   end;
   c[0]:=i;
   if x div 10=0 then dec(c[0])
   else c[i]:=x div 10;

end; procedure mul(a:bt;var c:bt); var i,x:longint; begin

   for i:=1 to c[0] do c[i]:=0;
   x:=0;
   for i:=1 to a[0] do begin
   x:=a[i]*(k-1)+x div 10+c[i];
   c[i]:=x mod 10;
   end;
   c[i+1]:=x div 10;
   c[0]:=a[0]+1;
   while (c[c[0]]=0)and(c[0]>1) do dec(c[0]);

end; begin

   readln(n);
   readln(k);
   f[0,0]:=1;
   f[0,1]:=1;
   f[1,0]:=1;
   f[1,1]:=k-1;
   for i:=2 to n do begin
   add(f[(i-1) mod 3],f[(i-2)mod 3],s);;
   mul(s,f[i mod 3]);
   end;
   for i:=f[n mod 3,0] downto 2 do write(f[n mod 3,i]);
   writeln(f[n mod 3,1]);

end. // by lv.wind