Practice on Toph

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

Expected Oddness

By shahriarsust13 · Limits 4s, 512 MB

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 (109+7). Output P⋅Q−1 mod (109+7).

Input

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 ≤ 105), the size of the string and the number of operations Alita will perform. The next line contains a string of n characters where each character is either ‘0’ or ‘1’.

It is guaranteed that the sum of all n doesn’t exceed 106.

Output

For each test case, output a single integer— P⋅Q−1 mod (109+7).

Sample

InputOutput
1
2 1
00
333333337

Discussion

Statistics


78% Solution Ratio

mohanr7073Earliest, 7M ago

Prakhar.888639Fastest, 0.1s

farhanhasinLightest, 131 kB

SwampFireShortest, 995B

Submit

Login to submit