Random Shuffle

A random shuffle function is described in the pseudocode below:

n = length of array A For i = 1 to n Generate a uniform random integer r between 1 and n inclusive Swap A[i] and A[r]

Find the probability that the given array was produced by performing the shuffle function on the integer array {1, 2, 3, ..., n}, where n is the number of elements in array.

Input

Each line is a sepate test case that contain the integer n (1 ≤ n ≤ 10) and the elements of array А - the permutation of numbers from 1 to n.

Output

For each test case print in a separate line with 8 digits after the decimal point the probabilty that the given array was produced by performing the shuffle function on the integer array {1, 2, 3, ..., n}.

Examples