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

To avoid manipulation by unauthorized persons, the lighting system has a special method to control the lights. Should one want to change the configuration of the lights, it is necessary to enter a binary number which gets added to the original configuration using standard integer summation.

You need a particular number of lights to be switched ON and you are curious what are your chances of success. How many suitable binary numbers are there?

#### Input Specification

The first line of input contains two integers and , representing the number of bits of and of , and the target number of lights to be switched ON. The second line contains a binary integer of length .

#### Output Specification

Print the number of different nonnegative -bit integers such that the sum has exactly bits set to 1. As the result might be large, output it modulo .

#### Sample Input 1

```
4 2
1100
```

#### Sample Output 1

`5`

#### Sample Input 2

```
10 5
1000100111
```

#### Sample Output 2

`260`

#### Sample Input 3

```
13 1
0000000000000
```

#### Sample Output 3

`13`

## Comments