#include <fstream>
using namespace std;
ifstream f ("sandokan.in");
ofstream g ("sandokan.out");
int n,k,v[5001],i,ma,h,j,a;
int main()
{
    f>>n>>k;
    for(i=1;i<=n;++i)
        f>>v[i];
        a=n;
        while(n>=k)
        {
            j++;
            n=n/k;
        }
        if(j>=2)
            n=n+1;
            n=n+a%k;
            n=n%k;
            ma=1;
            for(i=2;i<=n;++i)
                ma=ma*i%2000003;
g<<ma;
    return 0;
}