你有一个二进制串长度为N，串内包含0 和1 两个数字。现在用一种特殊的算法对该串进
行加密，加密方式是给定一个整数K 满足1 ≤ K ≤ N。对于该串内每个长度为K 的区间，计
算出该区间内数字的和，放进一个新序列里。新序列一共有N −K + 1 项，第i 项代表原序列
中第i 项到第i + K − 1 项的和。
现在给你加密后的序列，请你求出原序列有多少种不同的可能性？为了避免答案过大，请
你对1000003 取模。
1 ≤ N ≤ 106, 1 ≤ K ≤ N.
考虑根据给定的方程组，先确定可以确定的（注意，后面的关系可能会影响前面的），然后利用组合数计算。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010,mod=1000003;
int n,k,a[N];
char val[N];
void read(int &x){
x=0;
char c=getchar();
bool fh=0;
while(!isdigit(c)){
if(c=='-')fh=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-48;
c=getchar();
}
if(fh)x=-x;
}
ll qpow(ll a,int b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
freopen("bit.in","r",stdin);
freopen("bit.out","w",stdout);
read(n),read(k);
memset(val,-1,sizeof val);
for(int i=1;i<=n-k+1;++i){
read(a[i]);
// printf("%d\n",a[i]);
if(a[i]<0||a[i]>k){
puts("0");
return 0;
}
}
for(int i=2;i<=n-k+1;++i){
if(abs(a[i]-a[i-1])>1){
puts("0");
return 0;
}
//i-1 and i+k-1
if(a[i]!=a[i-1]){
val[i-1]=a[i]<a[i-1];
int fst=(i-1)%k;
if(!fst)fst+=k;
if(!~val[fst])val[fst]=val[i-1];
}
}
int tot=a[1],cnt=k;
for(int i=1;i<=k;++i)
if(~val[i])tot-=val[i],--cnt;
//C(cnt,tot)
// printf("%d %d\n",tot,cnt);
if(tot<0||cnt<0||cnt<tot){
puts("0");
return 0;
}
ll fz=1;
for(int i=1;i<=cnt;++i)fz=fz*i%mod;
ll fm=1;
for(int i=1;i<=tot;++i)fm=fm*i%mod;
for(int i=1;i<=cnt-tot;++i)fm=fm*i%mod;
printf("%lld",fz*qpow(fm,mod-2)%mod);
return 0;
}