String Game

Grisha and Dima are playing a game again. This time they have a string of zeros and ones. The following operations can be performed on the string:

• delete three consecutive ones;
• delete two consecutive zeros;
• replace the substring "01" with the substring "10";
• replace the substring "10" with the substring "01".

For example, in one operation the string "00111" can become the strings "00", "111", and "01011".

Now the boys are interested in the following question: how many distinct strings of length $k$ can be obtained from the given string using the described operations. Grisha and Dima are busy with their exams, so they ask you to help them.

Given a string and a number $k$, determine how many distinct strings of length $k$ can be obtained from the given string using the described operations.

The first line contains a positive integer $t$ ($1 \le t \le 1000$), the number of test cases in the input. The descriptions of the test cases follow.

Each test case is described by two lines. The first line contains two positive integers $n$ and $k$ ($1 \le k \le n \le 100$), the length of the original string and the length of the string to be obtained. The second line contains a string of length $n$ consisting of zeros and ones.

Output $t$ lines. For each test case, output the number of strings of length $k$ that can be obtained from the given string using the described operations. Since the answer can be quite large, output it modulo $10^9 + 7$.