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 in C++


#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++){
        cin >> grid[i];
    }
    vector<vector<int>> dp(n, vector<int>(m, 0));
    if(grid[0][0]=='.') dp[0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]=='#') continue;
            if(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] << "\n";
    return 0;
}