Number of Distinct Paths in a Grid

You are given a grid with n rows and m columns, where each cell is either navigable water denoted by 'O' or an obstacle denoted by 'X'. Your task is to determine the number of distinct paths from the top-left corner (1,1) to the bottom-right corner (n,m). You can only move either right or down at any point in time. If the starting or ending cell is an obstacle, then there is no valid path.

The solution utilizes dynamic programming, and the recurrence relation is given by:

$$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$

provided that the cell \( (i,j) \) is navigable (i.e., contains an 'O').

inputFormat

The first line of input contains two space-separated integers n and m, representing the number of rows and columns of the grid respectively. The following n lines each contain a string of length m, where each character is either 'O' (indicating a cell that can be navigated) or 'X' (indicating an obstacle).

outputFormat

Output a single integer representing the number of distinct paths from the top-left cell to the bottom-right cell. If no such path exists, output 0.

## sample

3 3
OOO
OXO
OOO

2