Practice on Toph

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

Mr. X and His String

By shahriar_sust · Limits 3s, 512 MB

Mr. X found a string of length N, which contains only 0 and 1. He calculates the value of a string by counting the number of 1 in it.

He decided to play with this string. He will randomly pick a segment (l, r) from the string and toggle all the characters from l to r (toggle means 0 to 1, and 1 to 0). He will do this operation M times.

But he has a lot of works to do and doesn't have enough time to perform this M operations. So he is interested to know the expected value of the string, after performing M operations. Assume that probability of each segment being selected is same.

Input

First contains an integer t , denotes the number of test cases.

Each of the next two lines describe a test case.

First line of each test case contains two integer N and M .

Second line of each test case contains a binary string of N length.

Constraints:

  • 1<= t <= 100
  • 1<= N, M <= 1000

Output

For each test case, print the expected value of the string after performing M operation in a single line.

If the answer is

then print it as

Sample

InputOutput
1
2 1
00
333333337

Discussion

Statistics


67% Solution Ratio

IOI_StfuFfsEarliest, Mar '18

shahriar_sustFastest, 0.7s

IOI_StfuFfsLightest, 131 kB

IOI_StfuFfsShortest, 1626B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.