Недавно Вас повысили до ведущего научного сотрудника НАСА, Национальной ассоциации алгоритмов сортировки. Поздравляем! Ваша основная обязанность --- тестирование алгоритмов сортировки, которые разрабатывает Ваша команда. К счастью, в этом году у НАСА большой бюджет, и вы смогли купить несколько современных целых чисел, которые можно использовать для тестирования алгоритмов сортировки. Как ведущий ученый, вы хорошо знаете, что алгоритмы проверяются по их поведению при наихудших входных данных. Итак, чтобы протестировать алгоритмы сортировки, вам нужны как можно более неотсортированные последовательности. Для последовательности чисел $(a_1, . . ., a_n)$, будем говорить, что элемент $a_k$ отсортирован, если для всех индексов $j$ таких что $j > k$, $a_j \ge a_k$ и для всех индексов $j$ таких что $j < k$, $a_j \le a_k$. Например, в $$ (1, 3, 2, 3, 4, 6, 5, 5) $$ отсортированными элементами являются $1$, второе вхождение $3$ и $4$. Обратите внимание, что последовательность сортируется тогда и только тогда, когда отсортированы все ее элементы. Последовательность называется полностью несортированной, если ни один из ее элементов не отсортирован. Задана последовательность целых чисел. Какое количество полностью неотсортированных последовательностей можно получить, переставив ее элементы? Две последовательности $(b_1, ..., b_n)$ и $(c_1, ..., c_n)$ считаются различными, если существует некоторый индекс $i \in \{1, ..., n\} $, для которого $b_i\ne c_i$. Поскольку количество перестановок может быть очень большим, найдите его по модулю $10^9 + 9$. \InputFile Начинается с целого числа $n~(1 \le n \le 5000)$. Далее следует одна строка с $n$ целыми числами $a_1, ..., a_n~(0 \le a_i \le 10^9)$. \OutputFile Выведите одно целое число: количество полностью неотсортированных последовательностей, которые можно получить, переставив $a_i$ по модулю $10^9 + 9$.