You live on a circular road, L metres in length. Any point on the road can be referred to by a real number x (0 ≤ x < L), the distance along the road clockwise from its Northmost point to that point (in metres).
Fortunately for you, this road is served by public transportation! There are N bus stops at distinct, integral points along the road.
Unfortunately for you, due to budget cuts exactly K of these N stops will soon be removed. The group of K removed stops will be chosen uniformly at random from the set of all possible groups of K stops.
You'd like to calculate the expected distance you'll have to walk from a random point along the road, chosen uniformly at random from the interval [0, L), to the nearest of the remaining N - K bus stops, in metres.
Input
Input begins with an integer T, the number of roads. For each road, there is first a line containing the space-separated integers N, K, and L. Then follows a line containing a string of length L. This string consists of only the characters '0' and '1'. There is a bus stop at position x if and only if the (x + 1)th character of the string is '1'. Exactly N of the characters will be '1'.
Output
For the ith road, print a line containing "Case #i: " followed by the expected distance you'll have to walk from a random point to the nearest bus stop, in metres. You should output the exact answer modulo (10^9 + 7). That is, if the exact answer is a / b (where a and b are integers), you should output a * b^-1 mod (10^9 + 7) (where b^-1 is the modular inverse of b mod (10^9 + 7)).
Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 500,000
0 ≤ K < N
1 ≤ L ≤ 1,000,000
Explanation of Sample
In the first case, the single existing stop will remain untouched. If your starting position is smaller than 1 or greater than 5, you'll walk clockwise to it, for a distance of between 0m and 4m. Otherwise, you'll walk counterclockwise to it, also for a distance of between 0m and 4m. As such, your expected distance to walk will be 2m.
In the third case, one of the stops will be removed at random. Whichever one is removed, your situation will be similar to that of the first case - the distance you'll have to walk will be uniformly distributed between 0m and 4m, for an expected distance of 2m.
In the fourth case, the exact answer is 3.15 or 63/20, which is 550000007 when taken modulo (10^9 + 7).
Sample input
Code: Select all
5
1 0 8
01000000
2 0 8
00010001
2 1 8
00010001
3 1 15
000000111000000
5 2 33
100010000001100000000000100000000Code: Select all
Case #1: 2
Case #2: 1
Case #3: 2
Case #4: 550000007
Case #5: 695454554