#include<fstream>
using namespace std;
int n,k,i,x,j,t,a[20000],b;
const int r=2000003;
int main()
{
ifstream f("sandokan.in");
ofstream g("sandokan.out");

f>>n>>k; for(i=1;i<=n;i++) f>>x;

n--;k--; j=n-k+1;

a[0]=1; a[1]=1;

 for(t=0,b=n;b>=j;b--)

  {for(i=1;i<=a[0]||t;i++,t/=10)
    a[i]=(t+=a[i]*b)%10;

    a[0]=i-1;
  }
  for(t=0,b=1;b<=k;b++)

   {for(i=a[0];i>0;i--,t%=b)
     a[i]=(t=t*10+a[i])/b;

    for(;!a[a[0]]&&a[0]>1;a[0]--);
   }
t=0;
 for(i=a[0];i>0;i--)
  t=(t*10+a[i])%r;
  
g<<t;

f.close();
g.close();
return 0;
}