校园有 $n$ 个景点，景点被编号为 $1$ 到 $n$。第 $i$ 个景点会被赋予一个 $0$ 到 $d-1$ 的之间的整数权值 $a_i$，表示该景点的类型。
校园里阡陌交通，大一新生小 K 第一时刻在景点 $1$，然后他开始随意地漫步，假设某时刻他在第 $i$ 个景点，则下一时刻，小 K 会按照 $p_{i,j}$ 的概率随机选择一个 $j$，然后移动到景点 $j$ （保证 $\sum_{j=1}^n p_{i,j}=1$，也有可能$i=j$ ）。
在漫步 $N$ 个时刻以后，小 K 会把他所经过的景点类型全部下来，这样他会得到一个长度为 $N$ 的数列 $S$，$S$ 中每个数都在 $0$ 到 $d-1$ 之间。
小 K 很想研究，他最后得到的数列的概率分布。假设他所有得到的数列为 $S_1,S_2,\dots,S_m$ ，那么令 $q_i=P(S=S_i)$ 表示他得到的数列是 $S_i$ 的概率。
他想知道 $\sum_{i=1}^mq_i^2$ 的值，请你帮他解决这个问题。

第一行两个正整数 $n$ 和 $N$ ，表示景点个数和小 K 一共要走的时刻数。
接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行的第 $j$ 个数字表示 。
接下来一行一个数 $d$，表示景点的类型数。
再一行 $n$ 个 $0$ 到 $d-1$之间的数，依次表示每个景点的类型 $a_i$。

输出一行一个实数表示 $\sum_{i=1}^m q_{i,j}^2$ 的值。你的答案被判定为正确，当且仅当和标准答案的绝对误差不超过 $10^{-8}$ 。

2 2
0.5 0.5
0.5 0.5
2
0 1

0.500000000

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

0.667200000