Random shuffle#1584
You are given a permutation of length .
Consider the following random shuffling procedure applied to the initial array \{1, 2, \ldots, n\}.
For i = 1, 2, \ldots, n, the following operation is performed in order:
an index is chosen uniformly at random from to ;
the elements at positions and are swapped.
All choices of are independent. Therefore, there are exactly n^n equally likely sequences of random choices.
Determine the probability that after performing all operations, the resulting array is .
Each line represents a separate test. It contains an integer n~(1 \le n \le 10), followed by the elements of array — a permutation of numbers from to .
For each test, print the required probability in a separate line. The answer must contain at least digits after the decimal point.
Example 1