Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2018
Lighting
lighting.c, lighting.cpp, lighting.c11, Lighting.java, lighting.py
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 a.
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 b which gets added to the original configuration a 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 N and K (1 ≤ N ≤ 1000, 0 ≤ K ≤ N ), N
representing the number of bits of a and of b, and K the target number of lights to be switched
ON. The second line contains a binary integer a of length N .
Output Specification
Print the number of different nonnegative N -bit integers b such that the sum a + b has exactly
K bits set to 1. As the result might be large, output it modulo 109 + 7.
Sample Input 1
Output for Sample Input 1
42
5
1100
Output for Sample Input 2
Sample Input 2
260
10 5
1000100111
Sample Input 3
Output for Sample Input 3
13 1
13
0000000000000
