22058번 - Декартовы деревья 다국어

Недавно на лекции в университете Вася узнал, что такое декартово дерево. Декартово дерево — это двоичное дерево, в каждом узле которого хранятся два значения: ключ и приоритет. Оно является деревом поиска по множеству ключей и кучей на максимум по приоритетам, то есть

• ключ любой вершины в левом поддереве вершины v меньше, чем ключ вершины v;
• ключ любой вершины в правом поддереве вершины v больше, чем ключ вершины v;
• приоритеты сыновей вершины v не больше, чем приоритет самой вершины v.

На контрольной работе Васе досталась следующая задача: дано n пар чисел вида (ключ, значение), i-я из которых выглядит как (i, y_i), и нужно узнать, сколько существует способов построить декартово дерево, используя как ключ вершины i число i, а как приоритет — y_i. Поскольку это число может оказаться достаточно большим, требуется найти остаток от его деления на число 10⁹+7.

Два декартовых дерева считаются различными, если у них разные корни, или существует вершина, имеющая разных предков в этих деревьях.

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

Описание каждого теста состоит из двух строк. Первая строка содержит одно целое число n (1 ≤ n ≤ 2·10⁵) — количество вершин в дереве. Вторая строка содержит n целых чисел y_i (1 ≤ y_i ≤ 10⁹) — приоритет i-й вершины дерева.

Сумма n по всем тестам не превосходит 2·10⁵.

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