问题描述

给定 $n$ 个长度为 $m$ 的不同的 $01$​ 字符串 $s_1,s_2,…,s_n$。

一个长度为 $nm$ 的 $01$ 字符串 $S$ 是好的，当且仅当 $S[1:m],S[m+1:2m],…,S[(n-1)m+1:nm]$ 这 $n$ 个子串两两不同，且每个子串均为 $s_1,s_2,…,s_n$ 中的一个。

例如 $s_1=00,s_2=01$，那么好的字符串有 $0001,0100$，容易发现好的字符串共有 $n!$ 个。

小 $A$ 给出了一台 $01$ 编码机，当小 $A$ 按下 $0$ 时有 $p$ 的概率编码机打出 $0$，$1-p$ 的概率打出 $1$；当小 $A$ 按下 $1$ 时有 $p$ 的概率编码机打出 $1$，$1-p$ 的概率打出 $0$。

编码机最多打出 $nm$ 个字符，因此小 $A$ 希望其恰能打出一个好的字符串，已知小 $A$ 绝顶聪明，会根据当前编码机打出的结果动态调整自身策略，请问小 $A$ 最终能打出一个好的字符串的胜率。

输入格式

输入第一行，包含 $2$ 个正整数 $n,m$ 和一个至多六位小数 $p$。

之后 $n$ 行，每行给出一个 $m$ 个字符的 $01$ 串 $s_i$。

输出格式

输出一行，表示答案，如果你的答案与标准答案的绝对误差不超过 $10^{-9}$，则会被认为答案正确，否则答案错误。

样例输入1

3 2 0.5
00
01
10

样例输出1

0.093750000000

样例输入2

2 5 0.1234
01000
10100

样例输出2

0.305642115411

样例输入3

5 5 0.999
00000
00001
00010
00011
00100

样例输出3

0.984112560855

样例输入4

5 5 0.001
00000
00001
00010
00011
00100

样例输出4

0.984112560855

样例输入5

5 5 0.1
00000
00001
01010
01011
00100

样例输出5

0.163155870461

样例输入6

见下发文件。

样例输出6

见下发文件。

评测数据规模

对于 $30\%$ 的数据，$n \leq 2$。

对于 $60\%$ 的数据，$n \leq 18$。

对于所有测评数据，$1 \leq n,m \leq 1000,0 \leq p \leq 1$。