409573: GYM103637 A Agile permutation

You are given an integer $$$n$$$ and a permutation of numbers $$$p_1, p_2, ... , p_n$$$. You are also given two integers $$$a, b$$$. There are 2 types of operations. The first type: swap any two elements of the permutation for the price of $$$a$$$ coins. The second type: shuffle the permutation randomly for the price of $$$b$$$ coins. You are allowed to make any number of operations of each type in any order. Your goal is to get identity permutation($$$1, 2, ... , n$$$) from the given one. You need to find the mathematical expectation of the number of spent coins on achieving the goal with the optimal strategy.

The first line of the input file consists of numbers $$$n, a, b$$$, separated by spaces.

The second line contains the permutation $$$p$$$ of length $$$n$$$, elements are separated by spaces.

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

Output single number: the mathematical expectation of the number of spent coins. Your answer will be considered correct, if it's absolute or relative error don't exceed $$$10^{-9}$$$.

2 5 5
1 2

0.00000000000000000000

2 5 1
2 1

2.00000000000000000000