#include <iostream>
#include <fstream>

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

const int NMAX = 5'005;
const int MOD = 2'000'003;

int n,k,v[NMAX],x,pascal[2][NMAX];

int main(){
    
    f >> n >> k;
    
    for(int i = 1;i <= n;++i)
        f >> v[i];
    
    // aflu cate numere o sa ramana dupa aplicarea operatiilor
    
    int x = n;
    
    while(x > k)
        x = x - k;
    
    // elementele din v sunt unice
    // Calulez C(n - 1,x - 1)
    // n - 1 deoarece nu maximul mereu o sa se afle in secventa
    // x - 1 deoarece nu ma intereseaza maximul
    
    pascal[1][1] = 1;
    
    for(int i = 2;i <= n - 1;++i){
        int o = (i + 1) % 2;
        for(int j = 1;j <= i;++j)
            if(j == 1 || j == i)
                pascal[i % 2][j] = 1;
            else
                pascal[i % 2][j] = (pascal[o][j] + pascal[o][j - 1]) % MOD;
    }
    
    g << pascal[(n - 1) % 2][x - 1];
    
    return 0;
}