405411: GYM101954 F Lighting

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Lightingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

The first line of input contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 1000$$$, $$$0 \le K \le 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

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 $$$10^9 + 7$$$.

ExamplesInput
4 2
1100
Output
5
Input
10 5
1000100111
Output
260
Input
13 1
0000000000000
Output
13

加入题单

上一题 下一题 算法标签: