Probability of Casino Dice Games

In a cheating casino, there are \(N\) dice. The casino holds \(M\) games. In each game a die is thrown, but the identity of the die used is not known. Instead, we know the outcome of the throw in the \(i\)th game, denoted by \(O(i)\).

For the \(i\)th die, the probability of obtaining face \(j\) is \(A(i,j)\). After using the \(i\)th die, the probability that the next die used is the \(j\)th die is \(B(i,j)\). For the first game, the probability that the \(i\)th die is chosen is \(\pi(i)\).

Your task is to calculate the probability that the sequence of \(M\) games (with outcomes \(O(1),O(2),\dots,O(M)\)) occurs in this casino. Mathematically, if \(k_1,k_2,\dots,k_M\) denotes the sequence of dice used, the probability is given by:

[ P = \sum_{k_1=1}^{N}\sum_{k_2=1}^{N}\cdots\sum_{k_M=1}^{N} \left[\pi(k_1) \cdot A(k_1, O(1)) \cdot \prod_{i=2}^{M} B(k_{i-1}, k_i) \cdot A(k_i, O(i)) \right]. ]

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of dice and the number of games, respectively.

The second line contains \(M\) integers \(O(1), O(2), \dots, O(M)\) indicating the outcomes of the games. Each \(O(i)\) is an integer between 1 and 6.

The third line contains \(N\) floating-point numbers \(\pi(1), \pi(2), \dots, \pi(N)\) representing the initial probability to choose each die for the first game.

The next \(N\) lines each contain 6 floating-point numbers. The \(i\)th of these lines contains \(A(i,1), A(i,2), \dots, A(i,6)\), the probabilities for die \(i\) to roll faces 1 to 6.

The following \(N\) lines each contain \(N\) floating-point numbers. The \(i\)th line contains \(B(i,1), B(i,2), \dots, B(i,N)\), the probabilities of transitioning from die \(i\) to each die for the next game.

outputFormat

Output a single floating-point number representing the probability that the given sequence of \(M\) games occurs in the casino.

sample

2 2
1 2
0.5 0.5
0.1 0.2 0.3 0.1 0.2 0.1
0.2 0.1 0.2 0.2 0.2 0.1
0.3 0.7
0.6 0.4

0.0225