Distinct Shortest Paths in a Grid

Given a grid of size ( m \times n ) represented by ( m ) strings each of length ( n ), where '.' indicates an open cell and '#' indicates an obstacle, your task is to determine the number of distinct shortest paths from the top-left cell ( (0,0) ) to the bottom-right cell ( (m-1, n-1) ). Movement is allowed in four cardinal directions: up, down, left, and right. Two paths are considered distinct if they differ in at least one cell along the route. If no valid path exists, output escape impossible.

inputFormat

The input is given via standard input (stdin). The first line contains two integers ( m ) and ( n ) separated by a space. This is followed by ( m ) lines, each containing a string of length ( n ) representing a row of the grid.

outputFormat

Output via standard output (stdout) a single integer representing the number of distinct shortest paths from the top-left to the bottom-right cell. If there is no valid path, print escape impossible instead.## sample

3 3
...
.#.
...

2