科学家们最近发现了虫洞——这些宇宙中的物体可以让我们在星系和星系之间、恒星系之间进行极远距离的旅行。

科学家们已知有 n 个可以到达的星系。你现在位于编号为 1 的星系，需要前往编号为 n 的星系。要从星系 i 到星系 j，需要穿越一个虫洞 (i, j)，并且恰好在一个星际日后你将到达星系 j。

然而，所需的虫洞并不总是可用。每过一天，虫洞会随机出现或消失。但在同一天内，虫洞的状态保持不变。每个星际日，虫洞从星系 i 到星系 j 存在的概率为 p_{ij}。在任意时刻，你总是可以查明当前可用的所有虫洞。每一次，你可以选择利用当前可用的虫洞出发前往另一星系，或者选择等待一天，看看本星系第二天会有哪些可通往其他星系的虫洞。

你的任务是求出：若你采取最优策略，从星系 1 到星系 n 所需天数的期望值。保证该期望值存在。

输入的第一行为一个整数 n（1 \leq n \leq 1000），表示可到达的星系数。

接下来有 n 行，每行 n 个元素。第 i 行第 j 列的元素 p_{ij} 表示从星系 i 到星系 j 的虫洞每天出现的概率（以百分数形式给出，且为整数）。保证所有主对角线上的数值均为 100。

输出一个实数，表示在最优策略下，从星系 1 到星系 n 所需天数的期望值。你的答案若与标准答案的绝对误差或相对误差不超过 10^{-6}，即视为正确。

即：假定你的答案为 a，标准答案为 b，则判定条件为 \frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}。

说明/提示

在第二个样例中，从星系 1 到星系 2 的虫洞每一天以概率 0.3 出现。期望等待该事件发生所需天数为 \frac{1}{0.3}。