#include <fstream>

using namespace std;

ifstream f("sandokan.in");
ofstream g("sandokan.out");

int c[5005];
int n,k,i,nr;

int main()
{
    f>>n;
    f>>k;
    for(i=1;i<=n;i++)
    {
        f>>nr;
    }
    int x=(n-1)%(k-1);
    c[0]=1;
    c[1]=1;
    for(i=2;i<=n-1;i++)
    {
        c[0]=1;
        for(int j=i;j;j--)
        {
            c[j]=(c[j]=c[j-1])%2000003;
        }
    }
    g<<c[x];
}