题目描述
定义一个 $\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$。
输出格式
对于每组数据，输出一行一个整数，表示答案。
样例 1 输入
4 3 1 001 5 2 00101 30 10 010100110101001010010010011101 10 1000000000000 0010110101
样例 1 输出
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}$。