「Cfz Round 2」01 String

定义一个 $\tt{01}$ 串是合法的，当且仅当它的首字符为 $\tt 0$ 而尾字符为 $\tt 1$。我们继而定义一个 $\tt{01}$ 串 $T$ 的权值 $f(T)$ 为，将 $T$ 划分若干个连续的合法子串的方案数。 例如 $f(\tt{001}) = \text{1}$，因为它仅可以被分割为 $[\tt 001]$；$f(\tt{0101101}) = \text{4}$，因为它可以被分割为 $[\tt 0101101][01, 01101][01011, 01][01, 011, 01]$ 共四种不同的方案；而 $f(\tt{1001010101}) = \text{0}$。 给定一个长度为 $n$ 的 $\tt{01}$ 串 $S$。定义 $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}$，你需要求出 $f_k(1, n)$ 的值。 由于答案可能很大，所以你只需要输出答案对 $10^9+7$ 取模的结果。

**本题有多组测试数据。** 第一行输入一个整数 $T$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据： + 第一行输入两个整数 $n,k$，分别表示 $\lvert S\rvert$ 和给定的参数。 + 接下来一行，输入一个长度为 $n$ 的 $\tt{01}$ 串表示 $S$。

对于每组数据，输出一行一个整数，表示答案。

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

2
19
926292963
340558843

#### 「样例解释 #1」 对于第 $1$ 组数据，用表格的交叉点表示 $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$ | 其中： - $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$； 所以答案为 $2$。 #### 「数据范围」 设 $\sum n$ 表示单个测试点中 $n$ 的和。 对于所有数据，$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$，保证 $S$ 中只包含 $\tt{0}$ 和 $\tt{1}$。 **只有你通过本题的所有测试点，你才能获得本题的分数。**