Network Reliability

Input

The first line contains three integers $N$ ( $1 \leq N \leq 14$ 1 \leq N \leq 14), $M$ ( $0 \leq M \leq 100$ 0 \leq M \leq 100) and $P$ ( $0 \leq P \leq 100$ 0 \leq P \leq 100), separated by a single space. $N$ is the number of the vertices and $M$ is the number of the edges. $P$ is the probability represented by a percentage.

The following $M$ lines describe the edges. Each line contains two integers $v_{i}$ v_i and $u_{i}$ u_i ( $1 \leq v_{i}, u_{i} \leq N$ 1 \leq v_i, u_i \leq N). ( $v_{i}$ v_i, $u_{i}$ u_i) indicates the edge that connects the two vertices $u_{i}$ u_i and $v_{i}$ v_i.

Output

Output a line containing the probability with which the remaining graph is connected. Your program may output an arbitrary number of digits after the decimal point. However, the absolute error should be $1 0^{- 9}$ 10^{-9} or less.

Examples

Example 1

Loading