Побудова Бінарного Дерева Пошуку#3326
Бінарне Дерево Пошуку (БДП) — це бінарне дерево з коренем, яке має такі властивості:
Ліве піддерево містить лише вершини зі значеннями, що строго менші за значення в корені.
Праве піддерево містить лише вершини зі значеннями, що строго більші за значення в корені.
Усі значення у вершинах різні.
Ліве і праве піддерево також рекурсивно є бінарними деревами пошуку.
При вставці нової вершини використовується такий алгоритм:
Якщо дерево порожнє, нова вершина стає коренем і процес вставки завершується. Інакше перейти до кроку 2.
Встановити поточною вершиною корінь дерева.
Якщо значення нової вершини менше поточної вершини:
Якщо ліве піддерево поточної вершини порожнє, нова вершина стає лівим сином поточної вершини і алгоритм завершується.
Інакше встановити поточною вершиною корінь лівого піддерева і повернутися до кроку 3.
Якщо значення нової вершини більше поточної вершини:
Якщо праве піддерево поточної вершини порожнє, нова вершина стає правим сином поточної вершини і алгоритм завершується.
Інакше встановити поточною вершиною корінь правого піддерева і повернутися до кроку 3.
Структура БДП залежить від вхідної послідовності. Різні послідовності можуть породжувати різні структури, навіть якщо самі числа однакові.
Розглянемо послідовність 1 2 3. Отримаємо таке БДП:
Якщо вхідна послідовність буде 2 1 3, отримаємо дерево:
З іншого боку, різні вхідні дані можуть давати ту саму структуру БДП. Наприклад, послідовність 2 1 3 створить ту ж структуру БДП, що й послідовність 4 6 2. Тоді дерево буде таке:
За заданими вершинами БДП визначте, скільки існує різних вхідних послідовностей, що утворюють ту ж саму структуру БДП, що й задана. Вершини дерева приймають значення з діапазону .
Перший рядок містить кількість тестів (t \leq 100). Кожен тест починається з двох цілих чисел і (1 \leq n \leq m \leq 1000) — кількість вершин у БДП та максимальне значення діапазону відповідно. Наступний рядок містить цілих чисел a_i (1 \leq a_i \leq 1000) — послідовність, за якою побудовано БДП.
Для кожного тесту виведіть кількість різних послідовностей, які утворюють ту саму структуру БДП, вважаючи, що значення беруться з діапазону . Результат виводьте за модулем .
Примітка: Пояснення до другого тесту.
Існує вхідних послідовностей (дані взято з проміжку ), які формують одну й ту ж структуру БДП:
2 1 3
2 3 1
2 1 4
2 4 1
3 1 4
3 4 1
3 2 4
3 4 2
Приклад 1