For a field trip, Robbie the Ram and his classmates were sent to space to travel intergalactically to explore the universe. However, he realizes that he is lost and can no longer find his class. Looking up his location, he is in galaxy \(1\) and after contacting his school for help, he finds out that there are \(N\) galaxies in total and his classmates are in galaxy \(N\).

To travel from one galaxy to the other, there are wormholes scattered across the universe. Each wormhole, labeled \((i, j)\), will send Robbie from galaxy \(i\) to galaxy \(j\). However, wormholes are not always available. The wormhole \((i, j)\) have a probabilities of \(p_{ij}\) of existing in a given day. This means that if Robbie really wants to use a specific wormhole, and if that wormhole is nonexistent for the current day, he may wait until the next day to see if the wormhole will come back, given if the probability is greater than 0%.

It takes one day to use a wormhole to travel from one galaxy to the other. Since your teacher wants to plan the time to return back to Earth, Robbie wants you to calculate the expected time in days to reach galaxy \(N\), given that he acts optimally. It is guaranteed that this value exists.

Contraints

\(1 \le N \le 1000\)

Input Specification

The first line will contain integer \(N\). In the next \(N\) lines, there will be a \(N\) by \(N\) matrix, with the number at row \(i\) and column \(j\) be \(p_{ij}\), which is the percent probability for wormhole \((i, j)\) to exist on a given day.

Output Specification

Output the expected value of time in days he needs to travel from galaxy \(1\) to galaxy \(N\). Your answer will be considered correct if the absolute error does not exceed \(10^{-6}\).

Sample Input 1

3
100 50 50
0 100 80
0 0 100

Sample Output 1

1.750000000000000

Note for Sample 1

The output 1.750001 will still technically pass, same with 1.7500001, 1.75, etc.

Sample Input 2

2
100 30
40 100

Sample Output 2

3.333333333333333