Random Walk

Yuanfang is walking on a chain. The chain has n nodes numbered from 1 to n. Every second, he can move from node i to node j with probability:



c(i,j) is an element in a given parameter matrix which is n×m. (1 <= c(i, j) <= 9)
Yuanfang wants to know the expectation time for him to walk from node 1 to node n.

There are no more than 10 test cases.
In each case, there are two integers n (2 <= n <= 50000), m (1 <= m <= 5), in the first line, meaning that there are n nodes and the parameter matrix is n×m . There are m integers in each of the next n lines which describe the parameter matrix .
The input ends with 0 0.

For each case, output the expectation time for Yuanfang to walk from node 1 to node n in one line. The answer should be rounded to 2 digits after decimal point.

3 1
1
1
1
5 2
1 2
2 1
3 2
2 3
1 3
0 0

6.94
8.75

2013ACM-ICPC杭州赛区全国邀请赛