A. Agile permutation
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число $$$n$$$ и перестановка чисел $$$p_1, p_2, ... , p_n$$$. Также даны два числа $$$a, b$$$. Есть операции 2 типов. Первый тип: поменять местами любых два элемента перестановки за $$$a$$$ монет. Второй тип: поменять порядок элементов перестановки на случайный за $$$b$$$ монет. Можно совершить сколько угодно операций каждого типа в любом порядке. Необходимо получить из перестановки тождественную перестановку ($$$1, 2, ... , n$$$). Нужно найти для заданной перестановки при оптимальной стратегии матожидание количества потраченных монет для достижения цели.

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

Первая строка входного файла содержит числа $$$n, a, b$$$, разделенные пробелами.

Вторая строка содержит перестановку $$$p$$$ длины $$$n$$$, элементы разделены пробелами.

$$$$$$1 \le n \le 20$$$$$$ $$$$$$1 \le a, b \le 1000$$$$$$ $$$$$$1 \le p_i \le n$$$$$$

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

Выведите одно число: искомое матожидание количества потраченных монет. Ваш ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает $$$10^{-9}$$$.

Примеры
Входные данные
2 5 5
1 2
Выходные данные
0.00000000000000000000
Входные данные
2 5 1
2 1
Выходные данные
2.00000000000000000000