Binary Casino 的照明系统由一个非常复杂且安全的机制控制，该机制连接到一个中央控制台。在控制台上，每个灯的状态被存储为一位信息（0 表示对应的灯熄灭，1 表示灯点亮），因此大楼中所有灯的完整状态可以用一个二进制数 $a$ 来表示。

为了防止未经授权的人员进行操作，照明系统有一种特殊的控制灯光的方法。如果有人想要改变灯光的配置，必须输入一个二进制数 $b$，该数将通过标准的整数加法累加到原始配置 $a$ 中。

你需要让特定数量的灯处于点亮状态，并且你想知道成功的概率有多大。有多少个合适的二进制数 $b$？

输入格式

输入的第一行包含两个整数 $N$ 和 $K$（$1 \le N \le 1000$，$0 \le K \le N$），其中 $N$ 表示 $a$ 和 $b$ 的位数，$K$ 表示目标点亮的灯的数量。

第二行包含一个长度为 $N$ 的二进制整数 $a$。

输出格式

输出不同的非负 $N$ 位整数 $b$ 的数量，使得和 $a + b$ 的二进制表示中恰好有 $K$ 个位为 1。由于结果可能很大，请将其对 $10^9 + 7$ 取模后输出。

样例

输入 1

4 2
1100

输出 1

5

输入 2

10 5
1000100111

输出 2

260

输入 3

13 1
0000000000000

输出 3

13