#include <fstream>

using namespace std;

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

int n,k,r,i,j,x,d[5005];

int main()
{
    fin >> n >> k;
    r=n;
    while (r>=k) r-=(k-1);
    r--;
    for (i=1;i<=n;i++) fin >> x;
    n--;
    d[0]=1;
    for (i=1;i<=n;i++)
    {
        for (j=i;j>=1;j--)
        {
            d[j]=d[j]+d[j-1];
            d[j]%=2000003;
        }
    }
    fout << d[r];

    return 0;
}