D2. Раскраска графа инверсий (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 2000$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Последовательность $$$b_1, b_2, \ldots, b_k$$$ называется хорошей, если существует раскраска каждого индекса $$$i$$$ в красный или синий цвет так, чтобы для каждой пары индексов $$$i \lt j$$$, для которой $$$b_i \gt b_j$$$, назначенные $$$i$$$ и $$$j$$$ цвета были различны.

Вам дана последовательность $$$a_1, a_2, \ldots, a_n$$$. Вычислите количество хороших подпоследовательностей данной последовательности, включая пустую подпоследовательность$$$^{\text{∗}}$$$. Поскольку ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$Последовательность $$$b$$$ является подпоследовательностью $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — длина последовательности.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — саму последовательность.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую количество хороших подпоследовательностей по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
4
4 2 3 1
7
7 6 1 2 3 3 2
5
1 1 1 1 1
11
7 2 1 9 7 3 4 1 3 5 3
Выходные данные
13
73
32
619
Примечание

В первом наборе входных данных не хорошие подпоследовательности — это $$$[4, 3, 1]$$$, $$$[4, 2, 1]$$$ и $$$[4, 2, 3, 1]$$$. Поскольку всего существует $$$16$$$ подпоследовательностей, это означает, что хороших подпоследовательностей: $$$16 - 3 = 13$$$.

В третьем наборе входных данных каждая подпоследовательность является хорошей.