E. Non-adjacent Swaps
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Найдите их количество, а также сумму расстояний от начальной перестановки до всех достижимых.

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

В первой строке содержится число $$$n$$$ ($$$1 \le n \le 100$$$) — число элементов перестановки. Вторая строка содержит $$$n$$$ различных чисел $$$a_i$$$ ($$$1 \le a_i \le n$$$) — начальную перестановку.

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

Выведите два числа — количество перестановок, которые можно получить, а также сумму расстояний от начальной до всех достижимых. Выведите оба числа по модулю $$$1\,000\,000\,007$$$.

Система оценки
ПодзадачаБаллыОграничения
115$$$n \le 8$$$
220$$$n \le 15$$$
330$$$n \le 30$$$
420$$$n \le 50$$$
515Без дополнительных ограничений
Примеры
Входные данные
4
3 1 4 2
Выходные данные
5 5
Входные данные
5
1 2 3 4 5
Выходные данные
1 0
Входные данные
6
5 3 1 2 4 6
Выходные данные
61 218
Примечание

В первом примере из начальной перестановки можно получить следующие:

  • $$$\lbrack 3, 1, 4, 2 \rbrack$$$, за 0 операций;
  • $$$\lbrack 3, 1, 2, 4 \rbrack$$$, за 1 операцию;
  • $$$\lbrack 1, 3, 4, 2 \rbrack$$$, за 1 операцию;
  • $$$\lbrack 3, 4, 1, 2 \rbrack$$$, за 1 операцию;
  • $$$\lbrack 1, 3, 2, 4 \rbrack$$$, за 2 операции (меняются местами элементы со значениями $$$(3, 1)$$$ и $$$(4, 2)$$$).

Всего пять перестановок, сумма расстояний до них также равна пяти.

Во втором примере никакие два элемента нельзя поменять местами, поэтому достижима только одна перестановка с расстоянием 0.