## CTU Open Contest 2018 - Lighting

View as PDF

Points: 12
Time limit: 0.6s
Memory limit: 256M

Problem type

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 ( the corresponding light is off, 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