Lighting

Time limit2sMemory limit512 MB

Summary

Count N-bit b such that standard addition a+b yields exactly K set bits, using digit DP over the carries of the binary addition.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Math
Solved: No attempts yet

Problem

The lighting system in Binary Casino is controlled by a very complex and secure mechanism that is connected to a central control console. At the console, the state of each light is stored as one bit of information (0 means the corresponding light is off, 1 means the light is on), so the complete state of all lights in the building can be represented by a binary number a.

To prevent manipulation by unauthorized people, the lighting system has a special way of controlling the lights. To change the configuration of the lights, one must enter a binary number b, which is added to the original configuration a using standard integer addition.

You want a particular number of lights to be switched on, and you are curious about your chances of success. How many suitable binary numbers are there?

Input

The first line of input contains two integers N and K (1 ≤ N ≤ 1000, 0 ≤ K ≤ N). N is the number of bits of a and of b, and K is the target number of lights to be switched on. The second line contains a binary integer a of length N.

Output

Print the number of different nonnegative N-bit integers b such that the sum a + b has exactly K bits set to 1. Since the result may be large, output it modulo 109 + 7.

Examples3

Example 1
Input
```
4 2
1100
```
Expected output
```
5
```
Example 2
Input
```
10 5
1000100111
```
Expected output
```
260
```
Example 3
Input
```
13 1
0000000000000
```
Expected output
```
13
```