Homogenizing Magic Attributes

Every day, Xiao Ling organizes the books at Ling Nai An. Today there are n magic books arranged in a row on the table. Each book has a magic attribute and an index. Initially all books had the same magic attribute, but after repeated use the attributes changed. Now Xiao Ling wishes to make all the books share the same magic attribute again.

Kirisame Marisa has agreed to help. In each operation, she picks an ordered pair of distinct books a and b uniformly at random (each ordered pair among the n(n-1) possibilities has equal probability). Then she casts a transfer spell. With probability \(p_{a,b}\ (p_{a,b}\in (0,1])\) the magic attribute of book b will change to that of book a. Otherwise, the spell fails and nothing changes; that is, even though she selected books a and b, if the transfer is unsuccessful, the operation is wasted.

Your task is to calculate the expected number of operations required until all books have the same magic attribute.

Note: An operation is counted regardless of whether the transfer is successful. Also note that if a book undergoes a successful transfer but its original attribute is still present on some other book, the number of distinct attributes does not change.

Mathematically, if we denote the current state by a vector \(s=(s_1,s_2,\dots,s_n)\) where \(s_i\) is the magic attribute of the i-th book, then the process is as follows:

• If all \(s_i\) are equal, the process terminates.
• Otherwise, an ordered pair \((a,b)\) with \(a\neq b\) is chosen uniformly among the \(n(n-1)\) possibilities. If \(s_a\neq s_b\), with probability \(\frac{p_{a,b}}{n(n-1)}\) the state changes to \(s'\) where \(s'_b=s_a\) (and all other entries remain the same), and with probability \(1-\frac{p_{a,b}}{1}\) nothing happens.

Let \(E(s)\) denote the expected remaining number of operations when the state is \(s\). Then for non-homogeneous \(s\) we have:

[ E(s) = \frac{1 + \sum_{\substack{1\le a, b\le n\ s_a\neq s_b}} \frac{p_{a,b}}{n(n-1)},E(s^{(a,b)})}{\sum_{\substack{1\le a, b\le n\ s_a\neq s_b}} \frac{p_{a,b}}{n(n-1)}} ]

Here \(s^{(a,b)}\) denotes the new state after a successful transfer from book \(a\) to book \(b\) (i.e. \(s_b\) is replaced by \(s_a\)).

Please output the expected number (to at least 6 decimal places) of operations required to achieve homogenization.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10), the number of books.

The next line contains n integers representing the current magic attributes of the books. (These integers may be arbitrary.)

This is followed by n lines, each containing n real numbers. The j-th number on the i-th line represents \(p_{i,j}\). For all \(i\), \(p_{i,i}\) will be 0. It is guaranteed that for all \(i \neq j\), \(p_{i,j}\in (0,1]\).

All real numbers in the input are given with at most 6 digits after the decimal point.

outputFormat

Output a single line containing the expected number of operations required until all books have the same magic attribute. The answer should be printed with at least 6 digits after the decimal point.

sample

1
7
0

0.000000