Description

T大有$n$个景点，每个点会被赋予一个0到d-1的之间的整数，表示该景点的类型。

校园里阡陌交通，大一新生czk第一时刻在景点1，然后他开始随意地漫步，假设某时刻他在第$i$个景点，则下一时刻，川川会以概率$p _{i,j}$移动到景点j (保证)。

在漫步N个时刻以后，czk会把他所经过的景点类型全部下来，这样他会得到一个长度为$N$的数列$S$，$S$中每个数都在$0$到$d-1$之间。

czk很想研究，他最后得到的数列的概率分布。假设他所有得到的数列为$S_1,S_2,\cdots,S_m$，那么令


表示表示他得到的数列是Si的概率。

他想知道的值，请你帮他解决这个问题。

Input Format

第一行两个正整数$n$和$N$，表示景点个数和czk一共要走的时刻数。

接下来$n$行，每行$n$个数，第$i$行的第$j$个数字表示$p _{i,j}$。输入数据保证对于任意的$i$，满足。

接下来一行一个数$d$，表示景点的类型数。

再一行$n$个$0$到$d-1$之间的数，依次表示每个景点的类型。

Output Format

输出包括一行，表示的值，保留9位小数。

Sample

【样例输入1】

2 2
0.5 0.5
0.5 0.5
2
0 1

【样例输出1】

0.500000000

【样例输入2】

3 3
0.2 0.4 0.4
1 0 0
1 0 0
2
0 1 1

【样例输出2】

0.667200000

Hint

对于$30\%$的数据，$N \le 10,d \le 3$；

对于$50\%$的数据，$N \le 50$；

对于$100\%$的数据，$，，n \le 16，N \le 107，d \le 100