This can be solved by calculating the probability of given square P(i, j) being occupied after m ring bells for given single flea starting at position (k, l). We can then compute the complement of the union of this events that is for all P(∑(i,j)') = ∏(1 - P(i.j)) - De Morgan Law Of Unions. The probability of square (i,j) being unocuppied afetr m ring bells is just equal to this value: P'(i,j) = ∏(1 - P(i.j)) when multiplication is calculated over flea starting from every square (k,l) in the grid. The expected value is the sum of all P'(i,j). To speed things up we can use symmetry and use just upper left quarter of the square as the starting positions of the fleas.

Can somebody clearify output format?

It says P X Q(-1) mod (10^9 + 7), which makes very little sense as sample output is just single number, e.g. if I try 1.0000 instead - it will be wrong. Plus as number of cells is restricted to 40 x 40, final result will never be over 1600; which makes mod statement somehow reflecting precision of result.

Please, help.

For output a/b, does it want a*b mod (10^9 + 7)? It says Q^(-1) which is confusing because ab^(-1) = a/b.

Dynamic Programming times out. Must be a better way.
Markov Chains ?

Adjacent squares are squares that share an edge.