hackercupai/hackercup huggingface dataset:
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 **i**th 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 (109 \+ 7). That
is, if the exact answer is **a** / **b** (where **a** and **b** are integers),
you should output **a** * **b**-1 mod (109 \+ 7) (where **b**-1 is the modular
inverse of **b** mod (109 \+ 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 (109 \+ 7).