Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Alita found a string of **n** characters where each character of the string is either **‘0’** or **‘1’**. The *Oddness* of the string is the number of occurrences of **‘1’** in it.

Being stressed out at work she decided to play with the string. So she started to randomly pick a segment **[l, r]** such that **1 ≤ l ≤ r ≤ n** and toggle all the characters from index **l** to index **r** inclusive (toggle means replacing **‘0’** by **‘1’** and **‘1’** by **‘0’**). She will do this operation exactly **m** times.

But she has lots of work to do and doesn’t have enough time to perform these **m** operations. So now she is interested to know the expected *Oddness* of the array after performing exactly **m** operations. Assume that the probability of each segment being selected is the same.

We can show that the expected *Oddness* can be expressed as **P/Q**, where **P** and **Q** are coprime integers and **Q** isn’t divided by **(10 ^{9}+7)**. Output

The first line contains an integer **t(1 ≤ t ≤ 100)**, the number of test cases.

Each of the next two lines describes a test case.

The first line of each test case contains two integers **n** and **m(1 ≤ n, m ≤ 10 ^{5})**, the size of the string and the number of operations Alita will perform. The next line contains a string of

It is guaranteed that the sum of all **n** doesn’t exceed **10 ^{6}**.

For each test case, output a single integer— **P⋅Q ^{−1} mod (10^{9}+7).**

Input | Output |
---|---|

1 2 1 00 | 333333337 |

75% Solution Ratio

mohanr7073Earliest,

AnachorFastest, 0.1s

farhanhasinLightest, 131 kB

SwampFireShortest, 995B

Login to submit