program xc1;
 var i:integer;
  a0,a1,a2:longint;
  n,k:integer;
begin
 read(n,k);
 a0:=1;
 a1:=k-1;
 for i:=2 to n do
 begin
  a2:=(k-1)*(a0+a1);
  a0:=a1;
  a1:=a2;
 end;
 writeln(a2);
end.

 Your logic seems OK (I didn't check it, but it seems). Your problem
is that the numbers might (and will) be bigger than a longint (not in
the input but in the output).

number 1009 you must use int64
number 1012 you must use your own count arithmatic