There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is $\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}$.
There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, $\dots,$ towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

-----Constraints-----
- $2 \leq N \leq 8$
- -$1000 \leq x_i \leq 1000$
- -$1000 \leq y_i \leq 1000$
- $\left(x_i, y_i\right) \neq \left(x_j, y_j\right) ($if $i \neq j)$
- (Added 21:12 JST) All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
:
x_N y_N

-----Output-----
Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

-----Sample Input-----
3
0 0
1 0
0 1

-----Sample Output-----
2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.
The length of the path 1 → 2 → 3 is $\sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}$.
By calculating the lengths of the other paths in this way, we see that the average length of all routes is:
$\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142$...

见题面

见题面