#include<stdio.h>
long int n,k,f1[200],f2[200],f3[200],i,j,t,c;
void main()
{
  scanf("%ld",&n);
  scanf("%ld",&k);
  f1[0]=1;
  f2[0]=k-1;
  t=1;
   for(i=2;i<=n;i++)
    for(j=0;j<t;j++)
    {
     if((k-1)*(f1[j]+f2[j]+c)>999999&&j==t-1)
      {t++;
       f3[t]= (k-1)*(f1[j]+f2[j]+c)-(k-1)*(f1[j]+f2[j]+c)%999999;
    }
       else

     if((k-1)*(f1[j]+f2[j]+c)>999999)
      { c= (k-1)*(f1[j]+f2[j]+c)-(k-1)*(f1[j]+f2[j]+c)%999999;
    }
      else
       c=0;
      f3[j]=(k-1)*(f1[j]+f2[j]+c);
      f1[j]=f2[j];
      f2[j]=f3[j];

    }

   for(j=t-1;j>=0;j--)
   printf("%ld",f3[j]);
    }

Try to solve it with long arithmetics... Delete if's and then in a unique repeat function use long arithmetics and that's all.don't increase t just bind t:=j; and you will get AC...
also the sizes of arrays are 2000 and you should print the 2nd array i mean f2 not f3. good luck!

P.S. if you have questions i'll be glad to help you...