Unique Paths in a Grid with Obstacles

In this problem, you are given a grid of R rows and C columns. Each cell of the grid is either free (represented by a .) or blocked (represented by a #). Your task is to determine the number of unique paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (R-1, C-1)) moving only right or down. A path cannot pass through blocked cells.

If the starting or ending cell is blocked, the output should be Impossible.

The recurrence relation for counting the paths is given by:

where the state $dp_{i,j}$ counts the number of ways to reach cell $(i,j)$ provided that the cell is not blocked.

If there is no valid path, output should be Impossible.

inputFormat

The input consists of multiple test cases. For each test case:

• The first line contains two integers R and C representing the number of rows and columns.
• The following R lines each contain a string of C characters (either '.' or '#') representing the grid.

The input terminates with a line containing '0 0' which should not be processed.

Input is read from standard input (stdin).

outputFormat

For each test case, output the number of unique paths from the top-left to the bottom-right corner on a separate line. If no path exists (or if the start or end cell is blocked), output the string 'Impossible'.

Output is to be written to standard output (stdout).## sample

3 3
...
.#.
...
2 2
.#
##
0 0

2
Impossible