{"raw_statement":[{"iden":"statement","content":"定义一个 $\\tt{01}$ 串是合法的，当且仅当它的首字符为 $\\tt 0$ 而尾字符为 $\\tt 1$。我们继而定义一个 $\\tt{01}$ 串 $T$ 的权值 $f(T)$ 为，将 $T$ 划分若干个连续的合法子串的方案数。\n\n例如 $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\n给定一个长度为 $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)$ 的值。\n\n由于答案可能很大，所以你只需要输出答案对 $10^9+7$ 取模的结果。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据：\n\n+ 第一行输入两个整数 $n,k$，分别表示 $\\lvert S\\rvert$ 和给定的参数。\n+ 接下来一行，输入一个长度为 $n$ 的 $\\tt{01}$ 串表示 $S$。"},{"iden":"output","content":"对于每组数据，输出一行一个整数，表示答案。"},{"iden":"note","content":"#### 「样例解释 #1」\n\n对于第 $1$ 组数据，用表格的交叉点表示 $f_k(l, r)$ 的值：\n\n| $\\bm{k = 0}$ | $r = 1$ | $2$ | $3$ |\n| -----------: | :-----: | :-: | :-: |\n| $l = 1$ | $0$ | $0$ | $1$ |\n| $2$ | / | $0$ | $1$ |\n| $3$ | / | / | $0$ |\n\n| $\\bm{k = 1}$ | $r = 1$ | $2$ | $3$ |\n| -----------: | :-----: | :-: | :-: |\n| $l = 1$ | $0$ | $0$ | $2$ |\n| $2$ | / | $0$ | $1$ |\n| $3$ | / | / | $0$ |\n\n其中：\n\n- $f_1(2, 3)= f_0(2, 2) + f_0(2, 3) + f_0(3, 3)= 0 + 1 + 0 = 1$；\n- $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$；\n\n所以答案为 $2$。\n \n#### 「数据范围」\n\n设 $\\sum n$ 表示单个测试点中 $n$ 的和。\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}$。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**"}],"translated_statement":null,"sample_group":[["4\n3 1\n001\n5 2\n00101\n30 10\n010100110101001010010010011101\n10 1000000000000\n0010110101","2\n19\n926292963\n340558843"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}