Number of ways

There is an $N\times M$ grid in which there are $N$ rows and $M$ colums. A cell $(i,j)$ is defined as the $i^{th}$ row from the top and $j^{th}$ column from left. You are located at $(1,1)$ initially and can perform the following steps any number of times:

1. You can move any number of steps downwards.
2. You can move any number of steps towards the right.

There are some obstacles in the path.

You are initially located at $(1,1)$ and wants to reach $(N,M)$ but you are interested in knowing the number of ways you can reach $(N,M)$ from $(1,1)$. Since these numbers can huge, print it modulo $({10}^9+7)$.

Two ways are considered different if they have a different number of steps or differ in some positions.

Example:

Input: n=3,m=3,grid[][]={{.,.,.},{.,*,.},{.,.,.}};
Output: 8

Approach

Java

public class NumberOfWays {

    // define mode values
    final static long mod = (long) (1e9 + 7);

    public static void main(String args[]) {

        int n = 3;
        int m = 3;
        char grid[][] = { { '.', '.', '.' }, { '.', '*', '.' }, { '.', '.', '.' } };

        long dp[][] = new long[n][m];
        long sumrow[] = new long[n];
        long sumcol[] = new long[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '*')
                    dp[i][j] = 0;
                else if (i == 0 && j == 0)
                    dp[i][j] = 1;
                else if (i == 0)
                    dp[i][j] = sumrow[i];
                else if (j == 0)
                    dp[i][j] = sumcol[j];
                else
                    dp[i][j] = (sumcol[j] + sumrow[i]) % mod;
                if (dp[i][j] == 0) {
                    sumrow[i] = 0;
                    sumcol[j] = 0;
                } else {
                    sumrow[i] = (sumrow[i] + dp[i][j]) % mod;
                    sumcol[j] = (sumcol[j] + dp[i][j]) % mod;
                }
            }
        System.out.println(dp[n - 1][m - 1]);
    }

}