Problem Description

In the final round of the Tenka1 Programmer Contest 1999, $ N $ participants played a round-robin tournament, and their final rankings were determined by the results of the round-robin matches and their qualifying rankings.

In the final round, rankings were determined by the number of wins in the round-robin matches. If two participants had the same number of wins, the one with the higher qualifying rank was placed higher.

It is assumed that there are no participants with the same qualifying rank.

Andou-kun and Hashimoto-kun keep records of the round-robin matches, with each match recording two entries: "X-san won against Y-san" and "Y-san lost to X-san".

Andou-kun never makes mistakes in his records.

If Andou-kun records that "the person with qualifying rank $ i $ won against the person with qualifying rank $ j $", then $ A_{i,j} = 1 $, otherwise $ A_{i,j} = 0 $.

However, the probability that Hashimoto-kun correctly records a single entry is $ P = p / q $, and with probability $ 1 - P $, he misrecords the outcome.

Each record is considered an independent event.

For example, for a certain match, there is a probability of $ (1 - P)^2 $ that the outcome is recorded reversed, or a probability of $ P(1 - P) $ that both are recorded as winners.

When determining the number of wins in the round-robin matches for X-san from the match records, the number of records stating "X-san won against someone" is used.

Calculate the probability that the rankings derived from Andou-kun's match records match those derived from Hashimoto-kun's match records.

Input Format

The input is given from the standard input in the following format:

$ N $ $ p/q $ $ A_{1,1} $ $ A_{1,2} $ $ … $ $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ $ … $ $ A_{2,N} $ : $ A_{N,1} $ $ A_{N,2} $ $ … $ $ A_{N,N} $

Output Format

Output the probability of matching rankings as a decimal. Ensure a newline at the end of the output.

The answer is accepted if the absolute or relative error is within $ 10^{-8} $.

Sample Input and Output

Sample Input #1

2 2/3
0 1
0 0

Sample Output #1

0.888888888888889

Sample Input #2

2 4/6
0 0
1 0

Sample Output #2

0.444444444444444

Sample Input #3

5 0/1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0

Sample Output #3

0.000000000000000

Sample Input #4

5 4/7
0 1 0 0 1
0 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 1 1 1 0

Sample Output #4

0.0130979274004664

Notes/Hints

Constraints

• $2 \leq N \leq 30$
• $0 \leq p \leq q$
• $1 \leq q \leq 10$
• $A_{i,j} \in \{ 0, 1 \}$
• $ A_{i,i} = 0 $
• If $i \neq j$, then $ A_{i,j} + A_{j,i} = 1 $
• $ N $, $ p $, $ q $ are integers

见题面 Input 部分

见题面 Output 部分