### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

Let the matrix **P** satisfy **P _{i,j}** = the probability that Ciel is in

**j**-th node at time 1 if Ciel is in i-th node at time 0. Then, (

**P**)

^{t}_{i,j}is equal to the probability that Ciel is in

**j**-th node at time t if Ciel is in

**i**-th node at time 0.

At first, we need to compress the graph as the below figure. The compressed graph contains only the nodes having beautiful flowers, start node, and end node. And the weight of edges **Q _{i,j}** is the probability that Ciel goes from

**i**-th node to

**j**-th node, without visiting other nodes having beautiful flowers.

**Q**can be calculated as (

_{i,j}**P**

^{∞})

_{i,j}, where

**P**is the weight of the lower left of the below figure. Then we obtain the answers by calculating

_{i,j}**Q**

^{∞}corresponding the right graph of the below graph.

We may calculate **P ^{M}** instead of

**P**

^{∞}, where

**M**is an enough large integer. The expectation of the number of Ciel’s move can be around 30! (2

^{108}< 30! < 2

^{109}) for some graphs. (Think the graph that the edge from node

**i**to node j exists iff i+1 ≥

**j**.) Therefore,

**M**must be greater than 30!. For instance, 2

^{110}is enough.

One important thing for calculating **P ^{M}** is thinking about a numerical error. The sums of

**P**for all

_{i,k}**k**should be

**1**. But in the computer, this may be slight different from 1.

Therefore, the elements of **P ^{M}** will be 0 or inf. To avoid this trouble, a normalization is needed, that is, the sums of probabilities should be keep 1.

The total complexity for this algorithm is **O(N**^{4}*log **N**!).

Note that **P**^{∞} may be calculated by solving linear equations with Gaussian elimination. However, because Gaussian elimination is not good algorithm in terms of a numerical error, this method may get WrongAnswer. If a bignum arithmetic is used, this method also can be accepted.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.