Spring Tile

One morning you wake up inside a maze full of springs.

You do not know why you are in this unfamiliar place. Staying put and waiting for help is an option, but experience has taught you that if you linger in a maze like this, a gust will eventually blow and sweep you away. There is no way to judge how much time remains before the gust comes. So you decide that the best strategy is to act so that the expected number of moves needed to escape the maze is minimized.

You pick up an unknown scroll lying at your feet and try reading it, and by chance you perceive the entire map of the maze. Then, by drinking a herb you happen to have, you learn the locations of all traps. Apparently this maze has no dangerous monsters or traps other than springs.

The maze consists of several kinds of tiles arranged in a rectangle, and is represented as follows, for example.

########
#..##g.#
#*#.*#.#
#......#
#*s#*.*#
########

• .: floor. You can walk freely on it.
• #: wall. You cannot enter a wall.
• s: your starting position. The tile below it is floor.
• g: stairs. If you step on this tile, you have escaped the maze.
• *: spring. If you step on this tile, you are thrown randomly onto one of the floor tiles (excluding stairs and spring tiles). The probability of being thrown onto each floor tile is the same.

A tile is one of these five kinds.

You can move from the tile you are currently on to an adjacent tile one square up, down, left, or right. You cannot move diagonally.

Given the maze map, find the expected number of moves needed to escape the maze when you use the best strategy. Being thrown by a spring is not counted in the number of moves.

W H
c11 c12 ... c1w
c21 c22 ... c2w
::    :
ch1 ch2 ... chw

The first line of input contains integers $W$ ($3 \le W \le 500$) and $H$ ($3 \le H \le 500$), in that order, separated by a space. The integer $W$ is the width of the maze, and the integer $H$ is its height.

The following $H$ lines contain $W$ characters representing the maze map (not separated by spaces). The format of this part is as in the example above. In the data, s and g each appear exactly once. Also, the one-square border around the maze always consists of walls.

In the given maze, you may assume that no matter how you move and no matter where a spring throws you, you will never enter a state where escape is impossible even if the floor tiles to which springs throw you could be set arbitrarily.

Print the expected number of moves needed to escape when you use the best strategy. The output may contain error, but its relative error from the true value must be less than $10^{-9}$.