Problem Description

A $\tt{01}$ string is defined as valid if and only if its first character is $\tt 0$ and its last character is $\tt 1$. We further define the weight $f(T)$ of a $\tt{01}$ string $T$ as the number of ways to split $T$ into several consecutive valid substrings.

For example, $f(\tt{001}) = \text{1}$, because it can only be split as $[\tt 001]$; $f(\tt{0101101}) = \text{4}$, because it can be split in four different ways: $[\tt 0101101][01, 01101][01011, 01][01, 011, 01]$; while $f(\tt{1001010101}) = \text{0}$.

Given a $\tt{01}$ string $S$ of length $n$. Define $f_k(l, r) = \begin{cases} f(S_{l\dots r}) & k = 0 \\ \displaystyle\sum_{l\leq l' \leq r' \leq r} f_{k-1}(l', r') & k \gt 0\end{cases}$. You need to compute the value of $f_k(1, n)$.

Since the answer may be very large, you only need to output it modulo $10^9+7$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, denoting the number of test cases.

Then the test cases follow. For each test case:

• The first line contains two integers $n, k$, representing $\lvert S\rvert$ and the given parameter.
• The next line contains a $\tt{01}$ string of length $n$, representing $S$.

Output Format

For each test case, output one line with one integer, representing the answer.

4
3 1
001
5 2
00101
30 10
010100110101001010010010011101
10 1000000000000
0010110101

2
19
926292963
340558843

Hint

"Sample Explanation #1"

For the first test case, use the intersections in the tables to represent the values of $f_k(l, r)$:

Where:

• $f_1(2, 3)= f_0(2, 2) + f_0(2, 3) + f_0(3, 3)= 0 + 1 + 0 = 1$.
• $f_1(1, 3) = f_0(1, 1) + f_0(1, 2) + f_0(1, 3) + f_0(2, 2) + f_0(2, 3) + f_0(3, 3) = 0 + 0 + 1 + 0 + 1 + 0 = 2$.

So the answer is $2$.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test file.

For all testdata, $1 \leq T \leq 100$, $1 \leq n \leq 2\times 10^5$, $0 \leq k \leq 10^{18}$, $\sum n \leq 6\times 10^5$, and it is guaranteed that $S$ contains only $\tt{0}$ and $\tt{1}$.

Only if you pass all test points of this problem can you obtain the score for this problem.

Translated by ChatGPT 5