给定一个整数 $n$ 和一个排列 $p_1, p_2, \dots, p_n$。同时给定两个整数 $a, b$。 有两种类型的操作。第一种：交换排列中的任意两个元素，代价为 $a$ 个硬币。第二种：随机打乱排列，代价为 $b$ 个硬币。你可以按任意顺序执行任意次数的这两种操作。你的目标是从给定的排列得到恒等排列 $(1, 2, \dots, n)$。你需要求出在最优策略下，达到目标所花费硬币数量的数学期望。

输入格式

第一行包含三个整数 $n, a, b$，以空格分隔。 第二行包含长度为 $n$ 的排列 $p$，元素以空格分隔。

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

输出格式

输出一个数字：花费硬币数量的数学期望。如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则被视为正确。

样例

输入 1

2 5 5
1 2

输出 1

0.00000000000000000000

输入 2

2 5 1
2 1

输出 2

2.00000000000000000000