22055번 - Игра со строками 다국어

Гриша и Дима снова играют в игру. В этот раз у них есть строка из нулей и единиц. Со строкой можно делать следующие операции:

• удалить три подряд идущих единицы;
• удалить два подряд идущих нуля;
• заменить подстроку «01» на подстроку «10»;
• заменить подстроку «10» на подстроку «01».

Так, например, за одну операцию из строки «00111» можно получить строки: «00», «111» и «01011».

Теперь ребят интересует вопрос: сколько различных строк длины k можно получить из данной строки, применяя описанные операции. Гриша и Дима заняты сессией, поэтому они просят вас помочь им.

По данной строке и числу k определите, сколько различных строк длины k можно получить из заданной строки, используя описанные операции.

Первая строка содержит целое положительное число t (1 ≤ t ≤ 1000) — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Каждый тестовый пример описывается двумя строками. Первая строка содержит два целых положительных числа n и k (1 ≤ k ≤ n ≤ 100) — длину исходной строки и длину строки, которую требуется получить. Вторая строка содержит строку длины n, состоящую из нулей и единиц.

Выведите t строк. Для каждого тестового примера выведите количество строк длины k, которые можно получить из заданной применением описанных операций. Так как ответ может быть достаточно большим, выведите его по модулю 10⁹ + 7.