문자열 게임

그리샤와 디마는 다시 게임을 한다. 이번에는 0과 1로 이루어진 문자열이 있다. 문자열에 다음 연산을 할 수 있다.

• 연속한 1 세 개를 지운다.
• 연속한 0 두 개를 지운다.
• 부분 문자열 "01"을 부분 문자열 "10"으로 바꾼다.
• 부분 문자열 "10"을 부분 문자열 "01"으로 바꾼다.

예를 들어 한 번의 연산으로 문자열 "00111"에서 문자열 "00", "111", "01011"을 얻을 수 있다.

이제 두 사람이 궁금해하는 것은 다음 질문이다. 주어진 문자열에서 설명한 연산을 사용해 길이 $k$인 서로 다른 문자열을 몇 개나 얻을 수 있는가. 그리샤와 디마는 시험 때문에 바빠서 당신에게 도움을 청한다.

문자열과 수 $k$가 주어졌을 때, 주어진 문자열에서 설명한 연산을 사용해 얻을 수 있는 길이 $k$인 서로 다른 문자열의 개수를 구하라.

첫째 줄에 입력에 주어지는 테스트 케이스의 개수인 양의 정수 $t$ ($1 \le t \le 1000$)가 주어진다. 다음으로 테스트 케이스의 설명이 이어진다.

각 테스트 케이스는 두 줄로 설명된다. 첫째 줄에 두 양의 정수 $n$과 $k$ ($1 \le k \le n \le 100$)가 주어진다. 이는 원래 문자열의 길이와 얻고자 하는 문자열의 길이이다. 둘째 줄에 0과 1로 이루어진 길이 $n$의 문자열이 주어진다.

$t$개의 줄을 출력하라. 각 테스트 케이스에 대해 주어진 문자열에서 설명한 연산을 사용해 얻을 수 있는 길이 $k$인 문자열의 개수를 출력하라. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하라.