Cutting the Long Cake

Albert baked a long cake of length $n$. The cake is divided in advance into $n$ cells so that it can be split into $n$ equal parts, and some cells have fruit toppings.

For example, the figure below shows a cake with $n = 8$, where $0$ is a cell without a topping and $1$ is a cell with a fruit topping. As an integer array, this is $A = [0, 1, 1, 0, 0, 1, 1, 0]$. $A[i]$ is $1$ if the $i$-th cell has a topping and $0$ if it does not.

Albert wants to cut this cake exactly $k-1$ times to make $k$ pieces. The cuts must satisfy the following conditions.

• Condition 1: Every cake piece must contain the same number of cells with toppings.
• Condition 2: No cell or piece may be discarded.

For example, when $k = 2$, there are $7$ ways to cut the cake above without discarding any cell or piece. Three of them satisfy condition 1. Each piece has two cells with toppings in these ways.

As another example, the figure below shows two ways to cut a cake with $n = 5$, $A = [0, 1, 0, 1, 0]$, and $k = 2$ that satisfy both conditions.

Given $n$, $k$, and the array $A$ that shows whether each cell has a topping, count the number of ways to cut the cake that satisfy the conditions. The answer can be very large, so print it modulo $10^9+7$.

The first line contains the number of test cases $T$.

Each test case is given in two lines. The first line contains $n$ and $k$ separated by a space. The second line contains the array $A$ as a string of length $n$ with no spaces.

Print the answer for each test case on its own line.

• $1 \le T \le 10$
• $1 \le k \le n \le 1\,000\,000$