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 define the weight $f(T)$ of a $\tt{01}$ string $T$ as the number of ways to partition $T$ into a sequence of contiguous valid substrings.

For example, $f(\tt{001}) = \text{1}$, because it can only be partitioned as $[\tt 001]$; $f(\tt{0101101}) = \text{4}$, because it can be partitioned in four different ways: $[\tt 0101101]$, $[\tt 01, 01101]$, $[\tt 01011, 01]$, and $[\tt 01, 011, 01]$; while $f(\tt{1001010101}) = \text{0}$.

Given a $\tt{01}$ string $S$ of length $n$, we 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 find the value of $f_k(1, n)$.

Since the answer can be very large, output the result modulo $10^9+7$.

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

Each test case is described as follows:

• The first line contains two integers $n$ and $k$, representing $|S|$ and the given parameter, respectively.
• The next line contains a $\tt{01}$ string of length $n$ representing $S$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

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

Output 1

2
19
926292963
340558843

Note 1

For the first test case, the values of $f_k(l, r)$ are:

k=0: (l=1, r=1): 0, (l=1, r=2): 0, (l=1, r=3): 1 (l=2, r=2): 0, (l=2, r=3): 1 (l=3, r=3): 0

k=1: (l=1, r=1): 0, (l=1, r=2): 0, (l=1, r=3): 2 (l=2, r=2): 0, (l=2, r=3): 1 (l=3, r=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$;

Thus, the answer is $2$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases.

For all data, $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$. It is guaranteed that $S$ contains only $\tt{0}$ and $\tt{1}$.