#include <bits/stdc++.h>

using namespace std;

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

int n, k, comb[5002][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][0] = comb[i][i] = 1;
    for (int j = 1; j < i; j++)
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
  }
  fout << comb[n - 1][c - 1];
  return 0;
}