403385: GYM101147 K Touristic Trip

Johnny got tired of math and came to Egypt to do some tourism. He has a list of Egyptian cities, numbered from 0 to N - 1. He starts his visit in Cairo (Cairo has number 0). Then he will choose the next city to visit at random from the list, say Alexandria, and then, after visiting Alexandria, he will randomly decide the next city to visit, maybe Giza, etc.

Although his decision is made at random, he is not equally likely to choose any city. More precisely, if he is currently in city number i, he will choose city number j as the next city to visit with probability P[i, j], where P is an NxN matrix of real numbers.

Also, all over Egypt, only M types of possible postcards are sold: Views of the Pyramids are one type, Alexandria beach landscapes another type, etc. The postcard types are numbered from 0 to M - 1. Whenever Johnny reaches a city, he sends a postcard to his parents, that he chooses at random among the M types of postcards. However, not all postcards have an equal chance to be chosen.

When Johnny reaches city number r, he will choose postcard type number s with probability C[r, s] where C is an NxM matrix. (For example, if he is in Giza, he's more likely to send a postcard with a view of the Pyramids).

During his stay in Egypt, Johnny will travel from city to city exactly K - 1 times, and hence he will send exactly K postcards. Please note that it is possible that he visits the same city twice: For instance, he may visit Cairo, then Alexandria, then Giza, then Alexandria again. However, he won't go back to the same city immediately after visiting it (in other words, P[i, i] = 0 for all i).

You can assume that any decision Johnny takes about which city to visit next or what postcard to send depends probabilistically only on the city he is currently in.

You know the type of each of the K postcards Johnny sent, as well as the matrices P and C. You are also given an integer Q, and you are asked to determine the probability that Johnny was in city Z when he sent his Q^th postcard to his parents.

The first line of the input will consist of a single integer T, the number of test cases. Each test case will consist of the following: One line containing integers N, M, K, Q, Z where 1 ≤ N ≤ 20, 1 ≤ M ≤ 10, 1 ≤ K ≤ 15, 0 ≤ Q < K, and 0 ≤ Z < N, followed by N lines containing N real space-separated values, where the j^th value on the i^th line represents P[i,j]. followed by another N lines containing M real space-separated values, where the j^th value on the i^th line represents the value C[i,j].

Then a single line will follow, containing exactly K integers, the type of the K postcards that Johnny sent to his parents during his stay in Egypt, in the same order he sent them.

For each test case, a single real value, rounded to exactly 3 places after the decimal point, representing the probability that Johnny was in city Z just after he sent Q postcards to his parents.

1
3 3 3 2 1
0.00 0.75 0.25
0.10 0.00 0.9
0.1 0.9 0.00
0.2 0.3 0.5
0.1 0.01 0.89
0.2 0.3 0.5
0 1 2

0.889

The elements of arrays P and C are double values and contains no more than four places after the decimal point.