给定一个长度为 N 的二进制串（01 串）以及一个正整数 K。

按照从左到右的顺序，依次遍历给定二进制串的 N−K+1 个长度为 K 的子串，并计算每个遍历子串的各位数字之和。

将这 N−K+1个子串数字和按照子串的遍历顺序进行排列，得到的序列就是给定二进制串的 K-子串数字和序列。

注意，所有子串数字和均用十进制表示。

例如，当 K=4时，二进制串 110010 的 K-子串数字和序列为 2 2 1，分析过程如下：

• 依次遍历 110010 的所有长度为 4 的子串： 1100、1001、0010。
• 计算每个遍历子串的各位数字之和：1+1+0+0=2、1+0+0+1=2、0+0+1+0=1。
• 将所有子串数字和按顺序排列，最终得到 2 2 1。

现在，给定 N,K以及一个 K-子串数字和序列，请你计算一共有多少个不同的长度为 N的二进制串可以得到该 K-子串数字和序列。

数据保证：至少存在一个长度为 N 的二进制串可以得到该 K-子串数字和序列。

由于结果可能很大，你只需要输出对 10^6+3 取模后的结果。

第一行包含两个整数 N,K。

第二行包含 N−K+1个整数，表示给定的 K-子串数字和序列。

输入保证给定的 K-子串数字和序列一定合法，即至少存在一个满足条件的二进制串与之对应。

不难发现，长度为 K的子串的各位数字之和一定不小于 0且不大于 K。

1≤K≤N≤10^6