Expected Total Reward in Random Video Publishing

Wen Zhaoxue is about to publish n videos. Each video can belong to one of t categories. Initially, she has k points. The first video is fixed to be of type v and, when published, gives her an immediate reward of \(b_v \times k\) (i.e. her score remains unchanged).

For every subsequent video, suppose the previous video was of type \(i\) and the current video is chosen to be of type \(j\) (each type is chosen uniformly at random among all t types). Then immediately after publishing, her current score is multiplied by \(d_{i,j}\) (if it is the first video, no multiplication occurs). Then if her updated score is \(x\), she receives a reward of \(b_j \times x\).

Formally, let the initial score be \(s_1=k\). For the first video (of fixed type \(v\)), the reward is \(b_v \times k\) and the score remains \(k\). For each video \(i\) (\(i \ge 2\)), if the previous video was of type \(i\) and the current video is of type \(j\) (chosen uniformly at random), then the new score becomes \(s_i = s_{i-1}\times d_{i,j}\) and the reward gained is \(b_j\times s_i = b_j\times d_{i,j}\times s_{i-1}\).

Your task is to compute the expected total reward after publishing all n videos.

Hint: For \(i\ge2\), if we define \(M_{i,j}=d_{i,j}/t\) and \(G_i=\frac{1}{t}\sum_{j=1}^{t}d_{i,j}b_j\) (with indices appropriately shifted), then by linearity of expectation the extra reward (beyond the first video) from starting in state \(i\) can be computed as:

[ F(m,i)=\sum_{p=0}^{m-1}(M^pG)_i, \quad m=n-1. ]

Finally, the expected total reward is:

[ \text{Answer}=k\Big(b_v + F(n-1,v)\Big). ]

inputFormat

The first line contains four numbers: n, t, k and v (with \(1 \le v \le t\)), where \(n\) is the number of videos, \(t\) is the number of categories, \(k\) is the initial score, and \(v\) is the fixed type for the first video.

The next t lines each contain t numbers, representing the matrix \(d\). The \(j\)-th number in the \(i\)-th line is \(d_{i,j}\).

The last line contains t numbers representing the vector \(b\) (i.e. \(b_1, b_2, \dots, b_t\)).

outputFormat

Output a single number: the expected total reward. Answers within an absolute or relative error of \(10^{-6}\) are accepted.

sample

1 2 1 1
1 2
3 4
0.1 0.2

0.100000