MIT 1st Team Contest 2007

Mario lives in an N x M maze grid. In this maze there are coin boxes, monsters, pipe systems, and walls. Whenever Mario enters a cell containing a coin box, he jumps to hit the box and gets as many coins as there are in the box (coin boxes do not disappear or lose coins after being hit). When Mario enters a cell with a monster, he loses a life. Pipe systems are like teleporters: for each system there is exactly one exit with at least one (but possibly several) entrances leading to that exit. When Mario walks into the entrance to a pipe system he is teleported to that pipe system's unique exit. Walking into a pipe system's exit does nothing special. Finally, Mario cannot walk into walls.

Mario decides to play a game. In the beginning of the game he starts with three lives at some given position, and at each time step he looks at all neighboring cells (excluding walls) and chooses one neighboring cell uniformly at random to walk to (x neighbors y if x is directly above, below, to the left, or to the right of y). If Mario has no non-wall neighboring cells then he stays at his current location. The game is over when either Mario is out of lives or it is impossible for him to collect more coins. Help Mario figure out the expected number of coins he will earn in one play of the game.

Input

The first line of the input is "N M" (1 ≤ N,M ≤ 15), giving the dimensions of the maze. What follows are N lines, each of which are M characters in length. The ith line displays the contents of the cells in the ith row of the maze. Mario starts in the unique cell with an '$' (which, beside holding Mario, is otherwise an empty cell). Cells with monsters are designated with '!'. Cells with coin boxes are represented by a number between 0 and 9 (inclusive), which is the number of coins in that coin box. Each pipe system is associated with a distinct letter between 'a' and 'z' (inclusive). A pipe system's entrances are designated with lower case letters, and the unique exit for a given pipe system has the corresponding capitalized letter (e.g. a pipe system with entrances labeled 'c' has exactly one exit, and it is labeled 'C'). Every pipe system appearing in the maze is guaranteed to have exactly one exit and at least one entrance. The character '#' designates a wall, and '.' designates an empty cell that Mario can just walk through.

Output

If the expected number of coins Mario collects is infinite, output -1. Otherwise, output a single real number, the expected number of coins Mario collects before the game is over. Your answer should be accurate to within either an absolute or relative error of 10^-6 of the actual answer. Your output should be followed by a newline.

Example

Input:
2 3
$1!
a.A

Output:
3.000000000