Для одного из своих заказчиков компания «Рафт» обучила нейросеть, состоящую из $$$N$$$ слоёв. Вес каждого отдельного слоя равен $$$a_i$$$. Программисты могут проранжировать слои нейросети любым способом, однако недавно был открыт критерий, который гарантированно позволяет назвать построенную нейросеть качественной: последовательности весов в слоях образуют пилообразную последовательность. Числовая последовательность называется пилообразной, если каждый ее элемент (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность $$$4, 2, 5, 3$$$ является пилообразной, а $$$1, 2, 4, 3$$$ – нет, поскольку $$$1 \lt 2 \lt 4$$$. Сотрудников компании заинтересовал следующий вопрос: сколько качественных нейросетей может быть построено из имеющихся слоёв? Помогите им – напишите программу, которая по заданной последовательности весов слоёв определит, сколькими способами можно их переставить так, чтобы они образовывали пилообразную последовательность.
В первой строке содержится число $$$N$$$ $$$(1 \le N \le 5000)$$$ – количество слоёв в нейросети. Во второй строке содержатся числа $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$, разделённые пробелом, где $$$a_i$$$ равно весу $$$i$$$-го слоя. Гарантируется, что все веса попарно различны.
В единственной строке выведите число – количество способов расположить слои так, чтобы они образовывали пилообразную последовательность. Так как это число может оказаться большим, выведите остаток от деления количества способов на $$$10^9 + 7$$$.
35 9 7
4
410 6 1 7
10
В первом тестовом примере пилообразными будут следующие варианты размещения слоёв: $$$(5, 9, 7), (7, 5, 9), (7, 9, 5)$$$ и $$$(9, 5, 7)$$$
