In a two dimensional map Harry initially is standing at some point denoted by character ‘H’. Also there is a horcrux at some point of map denoted by character ‘X’. In order to protect that horcrux You-Know-Who has appointed several Death Eaters at certain points of map denoted by character ‘D’.

Harry need to find the horcrux but he is not knowing the exact position of horcrux and hence he will walk in any of the four direction (left, right, top, bottom) with equal probability from his position as long as he stays in map and not go to any place where Death Eaters reside. Points on which Harry can walk will be denoted by ‘W’ in map.

Harry is determined to find the horcrux and he will not stop until he finds it. You need to find expected number of steps Harry will take to find the horcrux.

There are 20 maps in “maps.txt”. For each map first its dimensions are given $m, n$ which indicates map size m×n .After which map is given in described format. NOTE : There always exist a path between Harry and horcrux for map given in input.

Let the sum of expected value for all map be P. Enter the value of floor$(P*10^3)$. Link to maps.txt