Background

Casinos are hugely profitable. Large casinos make money by controlling the fairness of games through the rules. Although the rules may look fair, they are actually slightly unfair. Because big casinos have heavy foot traffic and large cash flow, this slight unfairness is amplified enough to generate considerable revenue for the casino. At the same time, this unfairness sometimes does not come from the rules, but from the equipment. For example, a loaded die is different from a normal die: the probabilities of rolling the $Q$ faces are not the same. Sometimes, to keep customers from noticing, they may even change the die after each game.

Problem Description

A cheating casino has $N$ dice. In this casino, there may have been $M$ games. Each game consists of rolling a die to produce a face value. We do not know which die was used, but we do know the outcome $O(i)$ of the $i$-th game.

For die $i$, the probability of rolling face $j$ is $A(i, j)$. After using die $i$, the probability that the next game uses die $j$ is $B(i, j)$. In particular, for the first game, the probability of using die $i$ is $\pi(i)$.

Curious Xiao v asks you to compute the probability that these $M$ games occurred in this casino.

Input Format

The first line contains three positive integers $N, M, Q$.

The second line contains $N$ floating-point numbers, representing $\pi(i)$.

Lines 3 to $N+2$ contain $N \times Q$ floating-point numbers; in row $i+2$ and column $j$ is $A(i, j)$.

Lines $N+3$ to $2 \times N + 2$ contain $N \times N$ floating-point numbers; in row $N+2+i$ and column $j$ is $B(i, j)$.

Line $2 \times N + 3$ contains $M$ positive integers, representing the $M$ game outcomes $O_i$, i.e., the face values rolled in each game.

Output Format

Output the required probability, rounded to four decimal places.

3 10 3
1 0 0
0.03 0.03 0.94
0.02 0.02 0.96
0.99 0.005 0.005
0.01 0.99 0
0.05 0.05 0.90
0.98 0.002 0.008 
2 2 0 2 2 0 2 2 0 2

0.4483

Hint

Constraints and notes:

• For 30% of the testdata: $M \le 100$, $1 \le N$, $Q \le 10$.
• For 100% of the testdata: $1 \le M \le 1000$, $1 \le N$, $Q \le 50$.

The matrices $A, B$ and the vector $\pi$ satisfy the characteristic conditions of probability transitions.

Translated by ChatGPT 5