#include <fstream>
#include <vector>
#define MOD 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,v,a[4][5004];
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
        fin>>v;
    k=n%(k-1);
    a[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        a[i%2][0]=1;
        for(int j=1;j<=i;j++)
        {
            a[i%2][j]=a[(i-1)%2][j-1]+a[(i-1)%2][j];
            a[i%2][j]=a[i%2][j]%MOD;
        }
    }
    fout<<a[(n-1)%2][k-1]%MOD;
    return 0;
}