there is my program


var
c:array[0..1800] of real;
n,m,i ,fn:longint;
begin
readln(n,m);
c[0]:=1;
c[1]:=m-1;
i:=1;
repeat
i:=i+1;
{for i:=2 to n do   }
c[i]:=(m-1)*(c[i-1]+c[i-2]);
until i>=n;
writeln(c[n]:0:0);
end.

Because There is some testcases that have more than 1800 decimal digits.You should write Big int for this problem.