Background

In Gensokyo, Motoori Kosuzu not only frequently gets bumped into but also has to organize the books at Suzunaan, causing her many troubles.

Problem Description

Kosuzu organizes the books at Suzunaan every day. This time, there are $n$ magical books on the table, arranged in a row, each with a magical attribute and a number.

Initially, all the books have the same magical attribute, but due to repeated use, the attributes have changed, and Kosuzu wants to make all the books' magical attributes the same again.

This time, Kosuzu has asked Kirisame Marisa for help in organizing the books. Each time, Marisa can cast a selected magic that randomly chooses two books $a, b$ ($a$ is not equal to $b$).

After selecting these two books, Marisa will cast a transfer magic, which has a probability of $p_{a,b} \ (p_{a,b} \in (0,1])$ that the magical attribute of book $b$ will become the magical attribute of book $a$. That means there is a probability of $1-p_{a,b}$ that the transfer of magical attributes will not succeed, meaning the operation is ineffective.

Note that $p_{a,b}$ is the probability for the success of the transfer and is independent of the operation of randomly selecting two books.

Now, Kosuzu wants to know the expected number of operations required to make all the books' magical attributes the same. Due to the urgency, Kosuzu has asked you to help solve this problem, or she won't give you the points for this question.

Input Format

The first line is a string where the $i$-th character represents the magical attribute of the $i$-th book. Note that each book's magical attribute is any uppercase letter from $A$ to $Z$. (Let the length of the string be $n$).

From the second line to the $n+1$-th line, each line contains $n$ real numbers, where the $j$-th number on the $i$-th line represents $p_{i,j}$.

Output Format

The result, accurate to one decimal place.

Sample Input and Output

Input Sample #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

Output Sample #1

164.9

Input Sample #2

DSGAY
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

Output Sample #2

16.0

Notes/Hints

For the first $10\%$ of the data, $n \leq 10$, and there is at most one distinct magical attribute.

For another $20\%$ of the data, $n \leq 10$, and there are at most two distinct magical attributes, with one of them having at most one occurrence.

For $100\%$ of the data, $n \leq 2 \times 10^3$.

For all data, it is guaranteed that $\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$.

Source

MtOI2019 League (MtOI2019) T3

Problem Author: Qiuly

见题面 Input 部分

见题面 Output 部分