Problem 34: Robot Paths

Problem Statement: Given an n x m grid with obstacles represented by '#' and free cells represented by '.', count the number of ways to reach from the top-left cell (1,1) to the bottom-right cell (n,m) moving only right or down. Output the answer modulo 10^9+7.

Input

The first line contains two integers n and m. Each of the next n lines contains a string of m characters representing the grid.

Output

Print the number of paths modulo 10^9+7.

Examples


Input:
3 3
...
.#.
...

Output:
2

Solution Explanation

Method 1: Use dynamic programming where dp[i][j] counts the ways to reach cell (i,j) from the start, updating cells from top-left to bottom-right. Method 2: Use combinatorial math but account for obstacles, which is more complex; therefore DP is the preferred approach.

Solution in C++


#include 
#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector grid(n);
    for (int i = 0; i < n; i++){
        cin >> grid[i];
    }
    vector> dp(n, vector(m, 0));
    if(grid[0][0]=='.') dp[0][0] = 1;
    for(int i=0;i 0) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            if(j > 0) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    }
    cout << dp[n-1][m-1] << "
";
    return 0;
}