西斯锦标赛的规则是众所周知的。 n 西斯参加锦标赛。锦标赛开始时会随机选择两名西斯参加第一场战斗。当其中一人失败时,他的位置将由下一个随机选择的之前没有参加过战斗的西斯取代。难道西斯锦标赛的每一场战斗都以一名对手的死亡而告终吗?当唯一的西斯还活着时,锦标赛结束。
绝地伊万意外出现在西斯锦标赛的参赛者名单中。然而,他在原力光明面的技能非常强大,因此他可以影响参加者的选择,无论是开始锦标赛还是在每场战斗后取代失败者的位置。他当然不会错过这个利用的机会。帮助他计算胜利的概率。
输入
第一行包含一个整数 n (1 ≤ n ≤ 18) — 西斯锦标赛的参与者人数。
接下来的 n 行每行包含 n 个实数,它们形成一个矩阵 pij (0 ≤ pij ≤ 1)。它的每个元素 pij 是第 i 个参与者在决斗中击败第 j 个参与者的概率。
主对角线 pii 上的元素等于 0。对于所有不同的 i、j,等式 pij + pji = 1 成立。所有概率的给出不超过六位小数。
绝地伊万是参与者名单中的第一名。
输出
输出一个实数——绝地伊万在锦标赛后存活的概率。答案的绝对或相对误差不得超过 10 - 6。
示例
输入 #1
3 0.0 0.5 0.8 0.5 0.0 0.4 0.2 0.6 0.0
输出 #1
0.680000000000000