CF605E.Intergalaxy Trips

The scientists have recently discovered wormholes — objects in space that allow to travel very long distances between galaxies and star systems.

The scientists know that there are n galaxies within reach. You are in the galaxy number 1 and you need to get to the galaxy number n. To get from galaxy i to galaxy j, you need to fly onto a wormhole (i, j) and in exactly one galaxy day you will find yourself in galaxy j.

Unfortunately, the required wormhole is not always available. Every galaxy day they disappear and appear at random. However, the state of wormholes does not change within one galaxy day. A wormhole from galaxy i to galaxy j exists during each galaxy day taken separately with probability p__ij. You can always find out what wormholes exist at the given moment. At each moment you can either travel to another galaxy through one of wormholes that exist at this moment or you can simply wait for one galaxy day to see which wormholes will lead from your current position at the next day.

Your task is to find the expected value of time needed to travel from galaxy 1 to galaxy n, if you act in the optimal way. It is guaranteed that this expected value exists.

科学家最近发现了虫洞——一种存在于太空中的物体，能够实现在星系与恒星系统之间的超远距离旅行。

科学家已知目前可及范围内共有 $n$ 个星系。你身处编号为 $1$ 的星系，目标是抵达编号为 $n$ 的星系。要从星系 $i$ 前往星系 $j$，你需飞入虫洞 $(i,\,j)$，并恰好耗费一个“星系日”时间，即可抵达星系 $j$。

不幸的是，所需的虫洞并非始终可用。每个星系日，所有虫洞都会随机消失或出现。然而，在单个星系日内，虫洞的状态保持不变。对于任意一对星系 $i$ 和 $j$，虫洞 $(i, j)$ 在每个星系日独立地以概率 $p_{ij}$ 存在。你总能即时获知当前时刻哪些虫洞存在。在任意时刻，你有两种选择：

• 利用当前存在的某条虫洞，立即前往另一星系；
• 或静候整整一个星系日，以观察次日从你当前位置出发将有哪些虫洞可用。

你的任务是：在采取最优策略的前提下，求出从星系 $1$ 抵达星系 $n$ 所需时间的期望值。题目保证该期望值存在。

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of galaxies within reach.

Then follows a matrix of n rows and n columns. Each element p__ij represents the probability that there is a wormhole from galaxy i to galaxy j. All the probabilities are given in percents and are integers. It is guaranteed that all the elements on the main diagonal are equal to 100.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 表示可达星系的数量。

接下来是一个 $n$ 行 $n$ 列的矩阵。每个元素 $p_{ij}$ 表示从星系 $i$ 到星系 $j$ 存在虫洞的概率。所有概率均以百分比形式给出，且为整数。保证主对角线上的所有元素均为 $100$。

Print a single real value — the expected value of the time needed to travel from galaxy 1 to galaxy n if one acts in an optimal way. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出一个实数——即在采取最优策略的情况下，从星系 1 到星系 $n$ 所需时间的期望值。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

In the second sample the wormhole from galaxy 1 to galaxy 2 appears every day with probability equal to 0.3. The expected value of days one needs to wait before this event occurs is .

在第二个样例中，从星系 1 到星系 2 的虫洞每天出现的概率为 0.3。在该事件发生前需要等待的天数的期望值为 。