program my1009(input,output);
const Max=2000;
type myrecord=array[1..Max] of longint;
var
  N,K:byte;
  total:real;
  save:array[1..2] of myrecord;
  temp:myrecord;
  Mark:array[1..2] of longint;
procedure work;
  var work_i,work_j:byte;
  begin
    save[1,1]:=(k-1);
    mark[1]:=1;mark[2]:=0;
    for work_i:=2 to N do begin
      temp:=save[1];
      for work_j:=1 to mark[2] do
        save[1,work_j]:=save[2,work_j]*(k-1);
      for work_j:=1 to mark[1] do
        save[2,work_j]:=temp[work_j];
      Mark[1]:=Mark[1]+Mark[2];
      for work_j:=Mark[2]+1 to Mark[1] do
        save[1,work_j]:=temp[work_j-mark[2]]*(k-1);
      Mark[2]:=Mark[1]-Mark[2];
    end;
    total:=0;
    for work_i:=1 to mark[2] do total:=total+save[2,work_i];
    for work_i:=1 to mark[1] do total:=total+save[1,work_i];
    writeln(total:1:0);
  end;
begin
  read(n,k);
  work;
end.

I write it for 1013, so I use the Big Integers class.
but actually they are the same problem except for the Scale.

#include <iostream>
#include <cstring>

using namespace std;
////////////////////////////////////////////////////////////////
// this class is not efficient enough, but it's useful!
// BigNum
class BigNum {
    friend ostream& operator<<(ostream &out, const BigNum &rhs);
    friend const BigNum operator+(const BigNum &lhs, const BigNum
&rhs);
    friend const BigNum operator*(const BigNum &lhs, int digit);
public:
    BigNum();
    BigNum(int digit);
    BigNum& operator=(int digit);
    BigNum& operator+=(const BigNum &rhs);
    BigNum& operator*=(int digit);

private:
    static const int MAX_D = 500;
    int numbers[MAX_D];
};
const int BigNum::MAX_D;

BigNum::BigNum()
{
    memset(numbers, 0, sizeof(numbers));
}

BigNum::BigNum(int digit)
{
    memset(numbers, 0, sizeof(numbers));
    int carry = digit;
    for (int i = 0; i < MAX_D && carry != 0; ++i) {
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
}

BigNum& BigNum::operator=(int digit)
{
    int carry = digit;
    for (int i = 0; i < MAX_D && carry != 0; ++i) {
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}


BigNum& BigNum::operator+=(const BigNum &rhs)
{
    int carry = 0;
    for (int i = 0; i < MAX_D; ++i) {
        carry += (numbers[i] + rhs.numbers[i]);
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}

BigNum& BigNum::operator*=(int digit)
{
    int carry = 0;
    for (int i = 0; i < MAX_D; ++i) {
        carry += (numbers[i] * digit);
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}

ostream& operator<<(ostream &out, const BigNum &rhs)
{
    int idx = BigNum::MAX_D - 1;
    for ( ; (idx >= 0) && (rhs.numbers[idx] == 0); --idx) ;
    if (idx < 0) {
        return (out << 0);
    }

    cout << rhs.numbers[idx--];
    for ( ; idx >= 0; --idx) {
        if (rhs.numbers[idx] / 10 == 0)
            cout << "000";
        else if (rhs.numbers[idx] / 100 == 0)
            cout << "00";
        else if (rhs.numbers[idx] / 1000 == 0)
            cout << "0";
        out << rhs.numbers[idx];
    }
    return out;
}

const BigNum operator+(const BigNum &lhs, const BigNum &rhs)
{
    return BigNum(lhs) += rhs;
}

const BigNum operator*(const BigNum &lhs, int digit)
{
    return BigNum(lhs) *= digit;
}

const BigNum operator*(int digit, const BigNum &rhs)
{
    return BigNum(rhs) *= digit;
}

//////////////////////////////////////////////////////////////////////
////

const int MAX_N = 1800;
const int MAX_K = 10;

int N, K;

int main()
{
    cin >> N >> K;
    BigNum Fn1 = 1, Fn2 = K-1, Fn;

    BigNum *pfn1 = &Fn1, *pfn2 = &Fn2, *pfn = &Fn;
    for (int i = 2; i <= N; ++i) {
        *pfn = (K-1) * (*pfn1 + *pfn2);
        pfn1 = pfn2;
        pfn2 = pfn;
        pfn = pfn1;
    }
    cout << (*pfn2) << endl;
    //
    return 0;
}

var
  n,k,i               :byte;
  p1,p2,p3            :longint;
begin
  read(n,k);
  p2:=1; p1:=k;
  for i:=1 to n-2 do begin
    p3:=p1;
    p1:=(k-1)*(p1+p2);
    p2:=p3;
  end;
  writeln((k-1)*p1);
end.
~~~~~~~~~~~~~
wish it help you
Yours Aidin_n7
(happybird is nice name!)