题目描述

你被廉价通信组织雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法如下。

给定一个长度为 $N$ 的二进制字符串，以及一个满足 $K \le N$ 的正整数 $K$。这个字符串的 SMS 由 $N-K+1$ 个整数组成：

• 第一个数是前 $K$ 位的和；
• 第二个数是第 $2$ 位到第 $K+1$ 位的和；
• 依此类推；
• 最后一个数是第 $N-K+1$ 位到第 $N$ 位的和。

例如，当 $K=4$ 时，二进制字符串 110010 的 SMS 为 2 2 1，因为：

由于你还是新手，你的任务不是从给定的 SMS 中恢复原来的二进制字符串，而是计算有多少个二进制字符串可以形成这个 SMS。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$。

第二行包含 $N-K+1$ 个用空格分隔的整数，保证它至少是某个二进制字符串的 SMS。

输出格式

输出一个整数，表示与给定 SMS 对应的可能二进制字符串总数对 $10^6+3$ 取模的结果。

样例输入

7 4
3 2 2 2

样例输出

3

样例解释

长度为 $7$ 的可能字符串有：1011001、1101010 和 1110011。

数据范围与子任务

对于所有数据：

难度评估

综合难度：省选中档 / NOI Day1 T1~T2；Codeforces 约 2000。

这题的关键在于从相邻两个窗口和入手。设原二进制串为 $x_1,x_2,\ldots,x_N$，给定 SMS 为 $a_1,a_2,\ldots,a_{N-K+1}$。则有：

因此：

• 若 $a_{i+1}=a_i$，则 $x_i=x_{i+K}$；
• 若 $a_{i+1}=a_i+1$，则 $x_i=0,x_{i+K}=1$；
• 若 $a_{i+1}=a_i-1$，则 $x_i=1,x_{i+K}=0$。

这样可以把位置之间的关系建成若干连通块，或者按下标模 $K$ 的链处理。最后只需要考虑前 $K$ 位：其中一部分已经被强制为 $0/1$，剩下若干自由变量需要选出一定数量为 $1$，答案就是一个组合数。

主要考点：滑动窗口差分、并查集/连通块、组合数取模、边界情况 $K=1$ 与 $K=N$。

容易出错的地方：

1. 忘记处理 $K=N$ 时只有一个窗口的情况；
2. 没有注意 $N$ 可达 $10^6$，不能枚举所有二进制串；
3. 相邻窗口差值只能是 $-1,0,1$，但题目保证输入合法，因此程序可不做复杂判错；
4. 组合数需要对质数 $10^6+3$ 取模，且 $N<10^6+3$，可以预处理阶乘和逆元。