Statement is not available in English language
1. Задача A. Начало
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вещи собраны, такси вызвано, и вот Александр уже на вокзале в ожидании своих друзей. Совсем скоро они поедут в Могилев на свою последнюю респу. Подходя к своему поезду, они проходили мимо других поездов, на каждом из которых был свой номер. И вдруг с Александром решил поспорить его так себе друг Егор. Егор сказал, что Александр не сможет из номера поезда вычислить абсолютный номер.

Номер поезда представляет из себя массив натуральных чисел $$$a$$$ размера $$$n$$$.

Абсолютный номер поезда — это количество подпоследовательностей по модулю $$$10^9+7$$$, которые являются перестановками.

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

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

Каждый тест содержит несколько наборов входных данных. Первая строка теста содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$)  — длина массива, который представляет номер поезда соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), разделенных пробелами — номер поезда.

Пусть $$$S$$$ — это сумма $$$n$$$ по всем наборам входных данных.

Тогда гарантируется, что $$$S$$$ не превосходит $$$2\cdot10^6$$$.

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

Для каждого набора входных данных выведите абсолютный номер поезда.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$S \le 18$$$$$$7$$$
$$$2$$$$$$a_i \leq a_{i+1}-1$$$$$$11$$$
$$$3$$$$$$a_i \neq a_j$$$ для $$$i \neq j$$$$$$4$$$$$$2$$$
$$$4$$$$$$a_i \le 10$$$$$$18$$$
$$$5$$$$$$S \le 5000$$$$$$8$$$$$$1$$$
$$$6$$$Нет дополнительных ограничений$$$52$$$$$$1$$$ — $$$5$$$
Пример
Входные данные
2
3
1 2 1
3
1 2 3
Выходные данные
4
3
Примечание

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.

Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, $$$[3, 2, 1]$$$ — перестановки, а $$$[1, 1]$$$, $$$[4, 3, 1]$$$, $$$[2, 3, 4]$$$ — нет.