C. Нестабильные элементы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан отсортированный массив из целых чисел $$$[a_1, a_2, \dots, a_n]$$$. Мы можем выполнять с этим массивом любое количество операций следующего вида:

  • отметить первый элемент массива, а также все элементы, отличающиеся от своих соседей слева (то есть все такие элементы $$$i$$$, что $$$a_i \ne a_{i-1}$$$).
  • либо удалить все отмеченные элементы, либо раздвоить их (то есть заменить каждый отмеченный элемент на два таких же элемента).

Например, рассмотрим массив $$$[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$$$ (жирным выделены отмеченные элементы). Если удалить все отмеченные элементы, получится $$$[1, 1, 4]$$$, а если раздвоить их, получится $$$[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$$$.

Операции нельзя выполнять, если массив опустел. После каждой операции отметки с элементов убираются.

Назовём массив целых чисел $$$b$$$ достижимым, если его можно получить из массива $$$a$$$ каким-то количеством описанных операций. Ваша задача — посчитать количество достижимых массивов длины $$$k$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le n$$$). Обратите внимание, что массив является отсортированным.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество достижимых массивов $$$b$$$, имеющих длину $$$k$$$. Можно показать, что в ограничениях задачи ответ помещается в стандартный $$$32$$$-битный целочисленный тип.

Пример
Входные данные
10
1 5
1
4 5
1 1 2 2
3 1
1 1 1
4 8
1 2 3 4
8 6
1 1 1 2 2 2 2 2
6 3
1 1 2 2 3 3
10 7
1 1 1 2 2 3 3 3 3 4
12 5
1 1 1 1 2 2 2 3 3 4 4 4
6 5
1 1 2 2 3 3
3 1
1 2 2
Выходные данные
1
0
1
1
2
1
2
1
0
1
Примечание

В первом примере можно провести такую последовательность операций:

  • $$$[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$$$.

Во втором примере нельзя получить массив длины $$$5$$$.

В третьем примере можно провести такую последовательность операций:

  • $$$[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$$$.

В пятом примере можно получить массивы $$$[1, 1, 2, 2, 2, 2]$$$ и $$$[2, 2, 2, 2, 2, 2]$$$:

  • $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$$$;
  • $$$[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$$$.

В седьмом примере можно получить массивы $$$[1, 1, 1, 3, 3, 3, 3]$$$ и $$$[3, 3, 3, 3, 3, 3, 3]$$$.