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).
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.
For each test case, output a single integer— P⋅Q−1 mod (109+7).
| Input | Output |
|---|---|
1 2 1 00 | 333333337 |