#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s,c;
    public:
      dsu(){
        a.resize(200000),s.resize(200000);
        iota(a.begin(),a.end(),0);
        fill(s.begin(),s.end(),1);
      }
      dsu(int n){
        a.resize(n),s.resize(n),c.resize(n,-1);
        iota(a.begin(),a.end(),0);
        fill(s.begin(),s.end(),1);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      int size(T x){
        return s[leader(x)];
      }
      int color(T x){
        return c[leader(x)];
      }
      void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(s[y]<s[x])swap(x,y);
        if(c[y]<0)c[y]=c[x];
        s[y]+=s[x],a[x]=y;
      }
      bool same(T x,T y){
        return leader(x)==leader(y);
      }
      void ext(T x,bool b){
        c[leader(x)]=b;
      }
  };
}
const int p=1e6+3;
int f[1000001];
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%p*a%p;
    a=a%p*a%p,b>>=1;
  }
  return r;
}
int com(int n,int m){
  return f[n]*qpow(f[m]*f[n-m]%p,p-2)%p;
}
main(){
  ios::sync_with_stdio(false);
  int n,k,c1=0,c2=0; cin>>n>>k;
  for(int i=f[0]=1;i<=n;i++)
    f[i]=f[i-1]*i%p;
  vector<int> a(n-k+1);
  for(auto &i:a)cin>>i;
  IAOI_lib::dsu<int> d(n);
  for(int i=0;i<n-k;i++){
    if(a[i]==a[i+1])d.merge(i,i+k);
    else d.ext(i,a[i]>a[i+1]),d.ext(i+k,a[i]<a[i+1]);
  }
  for(int i=0;i<k;i++)
    c1+=d.color(i)<0,c2+=d.color(i)==1;
  cout<<com(c1,a[0]-c2)<<endl;
  return 0;
}