Background

MS is a very NB teammate of Legendary Grandmaster DiDiDi, There are endless stories about how they won the championship in various Grand Prix.

One day after they won the championship in GP of Zhijiang, MS went to Zhijiang food street to find what to eat tonight.

Through the traversal of the food street, he found a burger shop that uses robots to automatically add bread and ingredients.

The toppings of the burger include beef, pickled cucumber, etc., a total of $n$. MS likes each ingredient to a different degree, but what is more important is the combination of ingredients, and there are differences between different combinations and orders. Every time the robot adds a random topping to the burger, MS wants to score the existing burger according to his own taste. For example, adding a piece of beef may get $10$ points, and adding a pickled cucumber will bring it down to $2$ points, but the maximum score will not exceed $n$. MS summed up the rules if the current score is $i(1 ≤ i ≤ n)$, then basically there will be a probability of $a_{ij}$ becoming $j(1 ≤ j ≤ n)$, (starting with a score of $1$), MS wants to know the expected score of a burger with $10^{114514}$toppings added.

Formally, given a $n × n$ score transition probability matrix, you need to find the expected score after making $10^{114514}$ transitions.

Round your answer to the nearest integer.

Input

The first line contains an integer n, indicating the number of ingredients $1 ≤ n ≤ 100$.

The next n lines, each line has $n$ three decimal places, the ith line and the $j_{th}$ column indicate that the original score is $i$, and after adding an ingredient, there is a probability of $a_{ij} (0 < a_{ij} < 1)$to become $j$.

It is guaranteed that the sum of the probabilities of each row is $1$, that is, $∀_i∑\limits_ja_{ij} = 1$.

Output

Output a positive integer in the first line, indicating the expected score

Examples

3
0.100 0.100 0.800
0.400 0.500 0.100
0.100 0.400 0.500

2

Note

It can be obtained that after adding $10^{114514}$ ingredients, there is

• a probability of $0.212121$ to get $1$ points

• a probability of $0.373737$ to get $2$ points

• a probability of $0.414141$ to get $3$ points

Therefore the expected score is $1 × 0.212121 + 2 × 0.373737 + 3 × 0.414141 = 2.202018$, rounded to $2$.