题目描述

定义一个 $\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)$ 的值：

其中：

• $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}$。

只有你通过本题的所有测试点，你才能获得本题的分数。