P10310 "Cfz Round 2" 01 String

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$.

**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$.

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

#### "Sample Explanation #1" For the first test case, use the intersections in the tables to represent the values of $f_k(l, r)$: | $\bm{k = 0}$ | $r = 1$ | $2$ | $3$ | | -----------: | :-----: | :-: | :-: | | $l = 1$ | $0$ | $0$ | $1$ | | $2$ | / | $0$ | $1$ | | $3$ | / | / | $0$ | | $\bm{k = 1}$ | $r = 1$ | $2$ | $3$ | | -----------: | :-----: | :-: | :-: | | $l = 1$ | $0$ | $0$ | $2$ | | $2$ | / | $0$ | $1$ | | $3$ | / | / | $0$ | 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