#include <fstream>

using namespace std;

ifstream fin( "sandokan.in" );
ofstream fout( "sandokan.out" );

const int NMAX = 5000;
const int MOD = 2000003;
int dp[2][NMAX + 2];

int main() {
  int n, k, i, j, x;
  fin >> n >> k;
  for( i = 1; i <= n; ++i )
    fin >> x;
  dp[0][0] = dp[1][0] = 1;
  for( i = 0; i <= n; ++i ){
    for( j = 1; j < k; ++j )
      dp[i % 2][j] = (dp[(i + 1) % 2][j - 1] + dp[(i + 1) % 2][j]) % MOD;
  }
  fout << dp[(n - 1) % 2][(n - 1) % (k - 1)];
  return 0;
}