Counting Distinct Paths Avoiding Rivers

You are given a grid with R rows and C columns. Each cell in the grid is either passable (represented by a dot .) or contains a river (represented by an asterisk *). Your task is to count the number of distinct paths from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (R-1, C-1)) such that you never step into a river cell. In each step you can only move either right or down.

The dynamic programming recurrence can be expressed in LaTeX as follows:

If the starting cell or the ending cell contains a river (i.e. a *), then there is no valid path, and the answer is 0.

inputFormat

The first line of input contains two integers R and C separated by a space, representing the number of rows and columns respectively. This is followed by R lines, each containing a string of length C which represents a row of the grid. The character . indicates a safe cell, and * indicates a cell with a river.

outputFormat

Output a single integer denoting the number of distinct valid paths from the top-left corner to the bottom-right corner.

3 3
...
.*.
...

2