你受雇于廉价通信组织（Cheap Communication Organization, CCO），致力于一项通信突破：子消息和（sub-message sum, SMS）。这一革命性的想法运作如下。
给定一个长度为 $N$ 的二进制字符串，以及某个正整数 $K$（满足 $K \le N$），该字符串的 SMS 由 $N - K + 1$ 个和组成。序列中的第一个和是第 $1$ 到第 $K$ 位数字之和，第二个和是第 $2$ 到第 $K + 1$ 位数字之和，以此类推，直到最后一个和，即第 $N - K + 1$ 到第 $N$ 位数字之和。
例如，若 $K = 4$，二进制字符串 110010 的 SMS 为 2, 2, 1。这是因为 $1 + 1 + 0 + 0 = 2$，$1 + 0 + 0 + 1 = 2$，以及 $0 + 0 + 1 + 0 = 1$。
由于你是一名初级开发人员，你的任务不是从给定的 SMS 中找出原始的二进制字符串，而是计算有多少个二进制字符串可能形成该 SMS。
输入格式
第一行包含两个空格分隔的整数 $N$ 和 $K$，其中 $1 \le K \le N$。
第二行包含 $N - K + 1$ 个空格分隔的整数，表示至少一个二进制字符串的 SMS。
| 分数 | $N$ 的范围 | $K$ 的附加范围 |
|---|---|---|
| 3 分 | $1 \le N \le 10$ | $K \le 3$ |
| 3 分 | $1 \le N \le 10$ | 无 |
| 4 分 | $1 \le N \le 1\,000$ | $K \le 10$ |
| 4 分 | $1 \le N \le 10^6$ | $K \le 20$ |
| 4 分 | $1 \le N \le 10^6$ | $K \le 3\,000$ |
| 7 分 | $1 \le N \le 10^6$ | 无 |
输出格式
输出 $T$ 除以质数 $10^6 + 3$ 的余数，其中 $T$ 是对应于给定 SMS 的所有可能的二进制字符串的总数。
样例
输入 1
7 4 3 2 2 2
输出 1
3
说明 1
长度为 7 的可能字符串为 1011001、1101010 和 1110011。