题目描述

在幻想乡中，本居 小铃 (Motoori Kosuzu) 不仅经常被人撞，还要整理铃奈庵的书籍，她有很多烦恼。

小铃每天都会整理一次铃奈庵的书籍。这次桌子上有 $n$ 本魔法书，这些书一次排成一排，每本书有一个魔法属性和编号。

最开始这些书的魔法属性都是一样的，但是因为被人多次使用，魔法属性发生了变化，小铃想让所有书的魔法属性重新全部相同。

这次小铃找到了雾雨 魔理沙 (Kirisame Marisa) 帮忙整理书籍，每次魔理沙可以释放选定魔法，魔法会随机选择两本书 $a,b$（$a$ 不等于 $b$）。

选定这两本书后，魔理沙会释放转移魔法，使得有 $p_{a,b}\ (p_{a,b}\in (0,1])$ 的概率，第 $b$ 本书的魔法属性变成第 $a$ 本书的魔法属性。也就是说有 $1-p_{a,b}$ 的概率，使得你即使选定了 $a,b$ 两本书，但是魔法属性的转移不成功，意味着这次操作是无效的 。

注意 $p_{a,b}$ 是对于转移是否成功的概率，和随机选择两本书的操作互不影响。

现在小铃想知道，求期望操作多少次，才能使所有的书魔法属性都一样？由于时间紧迫，小铃找到了你，希望你可以帮其解决这个问题，不然小铃就不会给你这题的分了。

输入格式

第一行一个字符串，第 $i$ 个字符表示第 $i$ 本书的魔法属性，注意每本书的魔法属性为 A 到 Z 的所有的大写字母中的任意一字母（设字符串的长度为 $n$）。

第二行到第 $n+1$ 行，每行 $n$ 个实数，第 $i$ 行的第 $j$ 个数表示 $p_{i,j}$ 。

输出格式

结果，精确到小数点后 $1$ 位。

样例

NACLYFISHAKIOI
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0

164.9

数据范围与提示

子任务

对于前 $10\%$ 的数据，$n\leq 10$，且最多有一种不同的魔法属性。

对于另外 $20\%$ 的数据，$n\leq10$，且最多有两种不同的魔法属性，并且其中一种的魔法属性的个数小于等于 $1$ 。

对于 $100\%$ 的数据，$n\leq2\times 10^3$ 。

对于所有数据，满足 $\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$ 。

题目来源

迷途之家 2019 联赛 (MtOI2019) T3

出题人：Qiuly