#include <bits/stdc++.h>

using namespace std;

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

int n, k, comb[2][5002], x;
const int mod = 2000003;

int main()
{
  fin >> n >> k;
  for (int i = 1; i <= n; i++)
    fin >> x;
  int c = n;
  while (c >= k) {
    c -= (k - 1);
  }
  for (int i = 0; i <= n; i++) {
    comb[i % 2][0] = comb[i % 2][i] = 1;
    for (int j = 1; j < i; j++)
      comb[i % 2][j] = (comb[1 - i % 2][j] + comb[1 - i % 2][j - 1]) % mod;
  }
  fout << comb[(n - 1) % 2][c - 1];
  return 0;
}