Problem:
 Score : 100 points    Problem Statement There is a grid with H horizontal rows and W vertical columns.
Let (i, j) denote the square at the i -th row from the top and the j -th column from the left.  For each i and j ( 1 \leq i \leq H , 1 \leq j \leq W ), Square (i, j) is described by a character a_{i, j} .
If a_{i, j} is . , Square (i, j) is an empty square; if a_{i, j} is # , Square (i, j) is a wall square.
It is guaranteed that Squares (1, 1) and (H, W) are empty squares.  Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.  Find the number of Taro's paths from Square (1, 1) to (H, W) .
As the answer can be extremely large, find the count modulo 10^9 + 7 .      Constraints  H and W are integers.  2 \leq H, W \leq 1000  a_{i, j} is . or # .  Squares (1, 1) and (H, W) are empty squares.         Input Input is given from Standard Input in the following format:  H  W  a_{1, 1} \ldots a_{1, W}  :  a_{H, 1} \ldots a_{H, W}       Output Print the number of Taro's paths from Square (1, 1) to (H, W) , modulo 10^9 + 7 .        Sample Input 1 3 4
...#
.#..
....      Sample Output 1 3  There are three paths as follows:        Sample Input 2 5 2
..
#.
..
.#
..      Sample Output 2 0  There may be no paths.       Sample Input 3 5 5
..#..
.....
#...#
.....
..#..      Sample Output 3 24       Sample Input 4 20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................      Sample Output 4 345263555  Be sure to print the count modulo 10^9 + 7 .

Solution (Python):
MOD = int(1e9+7)

h, w = map(int, input().split())
dp = [[0]*w for i in range(h)]
dp[-1][-1] = 1

g = []

for i in range(h):
    g.append([i for i in input()])

for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
        if i == h-1 or j == w-1:
            if g[i][j] == "
                dp[i][j] = 0
            elif i == h-1 and j != w-1:
                dp[i][j] = dp[i][j+1]
            elif j == w-1 and i != h-1:
                dp[i][j] = dp[i+1][j]
        else:
            if g[i][j] == "
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
                
        dp[i][j] %= MOD
                
                
print(dp[0][0])

Solution (Python):
def solve(result,rows,cols):
    MOD=10**9+7

    t={"
    dp=[[1]*cols for i in range(rows)]
    dp[0][0]=1
    for j in range(1,cols):
        dp[0][j]=dp[0][j-1]*(1-t[result[0][j]])
    for i in range(1,rows):
        dp[i][0]=dp[i-1][0]*(1-t[result[i][0]])
        
    for i in range(1,rows):
        for j in range(1,cols):
            if result[i][j]=="
                dp[i][j]=0
            else:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            
            
    return dp[-1][-1]%MOD

        
    


value=[int(i) for i in input().split()]
rows,cols=value[0],value[1]
result=[]
for i in range(rows):
    t=input()
    result.append(t)

print(solve(result,rows,cols))

Solution (Python):
MOD = 10**9+7

H, W = map(int, input().split())
a = ['']*H
for i in range(H):
    a[i] = input()

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i+1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j+1 < W and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD

print(dp[H-1][W-1])

Solution (Python):
MOD = 10**9+7

H, W = map(int, input().split())
a = ['']*H
for i in range(H):
    a[i] = input()

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i+1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j+1 < W and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD

print(dp[H-1][W-1])

Solution (Python):
def main():
    H, W = list(map(int, input().split()))
    dp = [['0'] * (W + 2)] + [['0', ] + ['0' if a == '
    mod = 1000000007
    dp[1][1] = '1'
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if dp[h][w] == '.':
                dp[h][w] = str((int(dp[h - 1][w]) + int(dp[h][w - 1])) % mod)
    print(dp[H][W])

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
H, W = map(int, input().split())
field = [['
for i in range(H):
    field.append(list('
field.append(['

dp = [[0 for _ in range(W+2)] for _ in range(H+2)]
dp[H][W] = 1

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '
            continue
        else:
            dp[i][j] += dp[i][j+1] + dp[i+1][j]
        dp[i][j] %= MOD

print(dp[1][1])

Solution (Python):
import sys
buf = sys.stdin.buffer

import numpy as np
MOD = 10 ** 9 + 7

H,W = map(int,buf.readline().split())

grid = np.frombuffer(buf.read(),dtype='S1').reshape(H,-1)[:,:W]



MOD = 10 ** 9 + 7
dp = np.zeros(W, dtype = np.int64)
dp[0] = 1

for row in grid:
  
  wall = (row == b'
  
  dp[wall] = 0
  
  np.cumsum(dp, out = dp)
  
  sub = np.maximum.accumulate(dp * wall)
  dp -= sub
  dp %= MOD

answer = dp[-1]
print(answer)

Solution (Python):
H,W=map(int,input().split())
mod=10**9+7
grid=[]
for i in range(H):
    s=str(input())
    grid.append(s)
dp=[[0 for i in range(W)]for j in range(H)]
dp[0][0]=1
for i in range(H):
    for j in range(W):
        if (i+1 < H) and (grid[i+1][j]=="."):
            dp[i+1][j]+=dp[i][j]
        if (j+1 < W) and (grid[i][j+1]=="."):
            dp[i][j+1]+=dp[i][j]
print(dp[-1][-1]%mod)

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    dp = [[0 for _ in range(W)] for _ in range(H)]
    for w in range(W):
        if A[0][w] == '
            break
        dp[0][w] = 1
    for h in range(H):
        if A[h][0] == '
            break
        dp[h][0] = 1
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '
                continue
            dp[h][w] = (dp[h - 1][w] + dp[h][w - 1]) % MOD
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
a=[]
z=(10**9)+7
for _ in range(n):
    s=input()
    b=[str(x) for x in s]
    a.append(b)
dp=[[0 for i in range(m)]for j in range(n)]
dp[0][0]=1
for i in range(1,m):
    if dp[0][i-1]==1 and a[0][i]!='
        dp[0][i]=1
for i in range(1,n):
    if dp[i-1][0]==1 and a[i][0]!='
        dp[i][0]=1
for i in range(1,n):
    for j in range(1,m):
        if a[i][j]!='
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(dp[n-1][m-1]%z)

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)



























def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	
	dp = [-1]*m*n
	
	def count_paths(i, j):
		
		
		
		key = (i*m + j)
		
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		
		
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid3():
	MOD = pow(10,9) + 7
	H, W = read()
	 
	grid = [[0]*W for h in range(H)]
	grid[0][0] = 1
	 
	for h in range(H) :  
	  row = input()
	 
	  for w in range(W) :
	    if row[w] == '
	    if h > 0 : grid[h][w] += grid[h-1][w]
	    if w > 0 : grid[h][w] += grid[h][w-1]
	    grid[h][w] %= MOD
	print(grid[-1][-1]% MOD)


if __name__ == "__main__":
	
	grid3()

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)



























def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	
	dp = [-1]*m*n
	
	def count_paths(i, j):
		
		
		
		key = (i*m + j)
		
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		
		
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	
	grid()

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)



























def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	
	dp = [-1]*m*n
	
	def count_paths(i, j):
		
		
		
		key = (i*m + j)
		
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		
		
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	
	grid()

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)



























def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	
	dp = [-1]*m*n
	
	def count_paths(i, j):
		
		
		
		key = (i*m + j)
		
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		
		
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	
	grid2()

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)



























def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	
	dp = [-1]*m*n
	
	def count_paths(i, j):
		
		
		
		key = (i*m + j)
		
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		
		
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	
	grid2()

Solution (Python):
h,w=map(int,input().split())
li=[]
mod=10**9+7
for i in range(h):
  li.append(input())
dp=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
  if(li[i][0]=="
      break
  dp[i][0]=1
for j in range(w):
    if(li[0][j]=="
        break
    dp[0][j]=1
for i in range(1,h):
  for j in range(1,w):
    if li[i][j]==".":
      dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[h-1][w-1]%mod)

Solution (Python):
l=input().split()
r=int(l[0])
c=int(l[1])
l=[]
for i in range(r):
	s=input()
	l.append(s)
dp=[[0 for i in range(c)]for i in range(r)]
dp[0][0]=1
for i in range(1,r):
	if(l[i][0]=='
		dp[i][0]=0
		continue
	dp[i][0]=dp[i-1][0]
for j in range(1,c):
	if(l[0][j]=='
		dp[0][j]=0
		continue
	dp[0][j]=dp[0][j-1]
for i in range(1,r):
	for j in range(1,c):
		if(l[i][j]=='
			dp[i][j]=0
		else:
			dp[i][j]=dp[i-1][j]+dp[i][j-1]
			dp[i][j]%=1000000007
print(dp[r-1][c-1])

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    modulo = 10**9+7
    board = []
    for _ in range(H):
        board.append(input().strip())
    count = [[0]*W for _ in range(H)]
    count[0][0] = 1
    for i in range(H):
        for j in range(W):
            if board[i][j] == '.':
                if j > 0 and board[i][j-1] == '.':
                    count[i][j] = (count[i][j]+count[i][j-1])%modulo
                if i > 0 and board[i-1][j] == '.':
                    count[i][j] = (count[i][j]+count[i-1][j])%modulo
    return count[-1][-1]


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

h, w = map(int, rl().split())

li = []
dh = [0, -1]
dw = [-1, 0]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
for _ in range(h):
    li.append(rl().rstrip())
for i in range(h):
    for j in range(w):
        if li[i][j] == '
            continue
        a = 0
        for k in range(2):
            nh = i + dh[k]
            nw = j + dw[k]
            if nh < 0 or nw < 0:
                continue
            a += dp[nh][nw]
        if dp[i][j] == 0:
            dp[i][j] = a
print((dp[-1][-1]) % (10**9 + 7))

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '
            continue
        if i>=1:
            dp[i][j]+=dp[i-1][j]
        if j>=1:
            dp[i][j]+=dp[i][j-1]
        dp[i][j]%=mod
print(dp[-1][-1])

Solution (Python):
[h,w] = [int(i) for i in input().split()]
mod = 10**9+7
a = [["
for i in range(h):
    tmp = ["
    s = input()
    for j in range(w):
        tmp.append(s[j])
    tmp.append("
    a.append(tmp)
a.append(["

dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[i][1] == "
        addi = 0
    dp[i][1] += addi
addi = 1
for i in range(2,w+1):
    if a[1][i] == "
        addi = 0
    dp[1][i] += addi


for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])

Solution (Python):
def add(a, b):
    mod = 1e9+7
    c = a + b
    if c >= mod:
        c -= mod
    return c

H, W = [int(x) for x in input().split()]

sl = [input() for _ in range(H)]

dp = [[0 for _ in range(W)] for _ in range(H)]

dp[0][0] = 1 

for i in range(H):
    for j in range(W):
        for frm in [[i-1, j], [i, j-1]]:
            r, c = frm
            if r >= 0 and c >= 0 and sl[r][c] != '
                dp[i][j] = add(dp[i][j], dp[r][c])

print(int(dp[H-1][W-1]))


"""
using ll = long long; 
int add(int a, int b) {
    int MOD = 1e9 + 7;
    return (a + b) % MOD;
}
int main() {
    int H;
    int W;
    scanf("%d%d\n", &H, &W);
    vector<vector<int>> dp(H, vector<int>(W));
    vector<vector<bool>> is_wall(H, vector<bool>(W));
    for (int i = 0; i < H; i++) {
        scanf("\n");
        for (int j = 0; j < W; j++) {
            char ch;
            scanf("%c", &ch);
            //cout << i << " " << j << " " << ch << endl;
            if (ch == '
                is_wall[i][j] = true;
            }
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            //cout << i << " " << j << " " << is_wall[i][j] << endl;
            if (!is_wall[i][j]) {
                if (i - 1 >= 0) {
                    dp[i][j] = add(dp[i][j], dp[i-1][j]);
                }
                if (j - 1 >= 0) {
                    dp[i][j] = add(dp[i][j], dp[i][j-1]);
                }    
            }
        }
    }    
	printf("%d\n", dp[H-1][W-1]);
	return 0;
}



"""

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for _ in range(H)]

    dp = [[f_inf] * W for _ in range(H)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if A[h][w] != "
                if h - 1 >= 0 and w - 1 >= 0:
                    dp[h][w] = min(dp[h][w], ((dp[h - 1][w] if A[h - 1][w] == "." else 0) + (dp[h][w - 1] if A[h][w - 1] == "." else 0)) % mod)
                elif h - 1 >= 0:
                    dp[h][w] = min(dp[h][w], (dp[h - 1][w] if A[h - 1][w] == "." else 0) % mod)
                elif w - 1 >= 0:
                    dp[h][w] = min(dp[h][w], (dp[h][w - 1] if A[h][w - 1] == "." else 0) % mod)

    print(dp[H - 1][W - 1] % mod)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import numpy as np
from functools import lru_cache
from collections import deque




H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[i][j] == "
        dp[i][j] = 0
      else:
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

print(dp[H - 1][W - 1])

Solution (Python):
H,W = [int(i) for i in input().split()]
grid = [input() for i in range(H)]
dp = [[0]*(W+1) for i in range(H+1)]
for i in range(1,H+1):
    for j in range(1,W+1):
        if grid[i-1][j-1] == ".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if i == j == 1:
            dp[i][j] = 1
print(dp[-1][-1]%(10**9+7))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

H,W = map(int,input().split())
A = [input() for _ in range (H)]

MOD = 10**9+7
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][0] = 1
dp[1][1] = 1
for i in range(H):
    for j in range(W):
        if i==j and i==0:continue
        if A[i][j]=='.':
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            dp[i+1][j+1] %= MOD

print(dp[H][W])

Solution (Python):
N, M = map(int,input().split())
maze = [input() for _ in range(N)]
dp = [[0]*M for _ in range(N)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(M):
        if maze[i][j] != "
            if i-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod

print(dp[N-1][M-1])

Solution (Python):
H, W = map(int, input().split())
grid = [input() for i in range((H))]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
m = 10**9 + 7
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            continue
        if i >= 1:
            dp[i][j] += dp[i-1][j]
        if j >= 1:
            dp[i][j] += dp[i][j-1]

        dp[i][j] %= m

print(dp[-1][-1])

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '
            continue
        if i >= 1:
            dp[i][j] += dp[i - 1][j]
        if j >= 1:
            dp[i][j] += dp[i][j - 1]
        dp[i][j] %= mod
print(dp[-1][-1])

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '
            continue
        if i >= 1:
            dp[i][j] += dp[i - 1][j]
        if j >= 1:
            dp[i][j] += dp[i][j - 1]
        dp[i][j] %= mod
print(dp[-1][-1])

Solution (Python):
def grid(mat: list):
    m = len(mat)
    n = len(mat[0])
    dp = [[0 for _ in range(n)] for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if mat[i][j] == '.':
                if i > 0:
                    dp[i][j] = dp[i - 1][j]
                if j > 0:
                    dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]%1000000007


if __name__ == '__main__':
    m, n = list(map(int, input().split()))
    mat = [[]] * m
    for i in range(m):
        mat[i] = [c for c in input()]
    print(grid(mat))

Solution (Python):
h, w = map(int, input().split())

mat = []
dp = []
m = 10**9+7

for i in range(h):
    mat.append(list(input()))
    dp.append(list([0]*w))

dp[0][0] = 1


for x in range(h):
    for y in range(w):

        if x != 0 or y != 0:
            if mat[x][y] == "
                dp[x][y] = 0

            else:
                dp[x][y] = (dp[x - 1][y] + dp[x][y - 1]) % m

print(dp[h - 1][w - 1])

Solution (Python):
h, w = map(int, input().split())

mat = []
dp = []
m = 10**9+7

for i in range(h):
    mat.append(list(input()))
    dp.append(list([0]*w))

dp[0][0] = 1


for x in range(h):
    for y in range(w):

        if x != 0 or y != 0:
            if mat[x][y] == "
                dp[x][y] = 0

            else:
                dp[x][y] += (dp[x - 1][y] + dp[x][y - 1]) % m

print(dp[h - 1][w - 1])

Solution (Python):
h,w = map(int,input().split())

z = []
p = []
m = 10**9+7
for i in range(h):
    z.append(list(input()))
    p.append(list([0]*w))
p[0][0] = 1

for x in range(h):
    for y in range(w):
        if x != 0 or y != 0:
            if z[x][y] == "
                p[x][y] == 0
            else:
                p[x][y] += (p[x-1][y] + p[x][y-1])%m
               
                
print(p[h-1][w-1])

Solution (Python):
mod = 10**9+7


def main():
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]
    dp = [[0 for _ in range(W)] for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if i != 0 or j != 0:
                if a[i][j] == ".":
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                    dp[i][j] %= mod
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Solution (Python):
mod = 10**9+7


def main():
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]
    dp = [[0 for _ in range(W)] for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j] == ".":
                if j+1 < W:
                    dp[i][j + 1] += dp[i][j]
                    dp[i][j+1] %= mod
                if i+1 < H:
                    dp[i + 1][j] += dp[i][j]
                    dp[i+1][j] %= mod
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Solution (Python):
h,w=map(int,input().split())
m,mod=[],10**9+7
for i in range(h):m.append(input())
dp=[[0]*w for i in range(h)]
dp[0][0]=1
for i in range(h):
	for j in range(w):
		if m[i][j]=='.':
			if i==0 and j!=0:dp[i][j]=dp[i][j-1]
			elif i!=0 and j==0:dp[i][j]=dp[i-1][j]
			elif i!=0 and j!=0:dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[h-1][w-1])

Solution (Python):
H, W = map(int, input().split())
grid = []
for h in range(H):
  S = input()
  tmp = []
  for s in S:
    tmp.append(s)
  grid.append(tmp)


dp = [[0]*W for _ in range(H)]
dp[H-1][W-1] = 1

for h in reversed(range(H)):
  for w in reversed(range(W)):
    if (h+1) <= (H-1):
      dp[h][w] += dp[h+1][w]
    if (w+1) <= (W-1):
      dp[h][w] += dp[h][w+1]
    if grid[h][w] == "
      dp[h][w] = 0
    
      
print(dp[0][0] % (10**9 + 7))

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

H,W = MI()
V = [list(ST()) for _ in range(H)]
dp = FILL2(0,H+1,W+1)
dp[1][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        if V[i-1][j-1] == '.' and (i!=1 or j!=1):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD
print(dp[H][W])

Solution (Python):
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
mod=10**9+7
chk=[[0] for f in range(H)]
ans=[[0 for e in range(W)] for f in range(H)]
ans[0][0]=1
for i in range(H):
 chk[i]=[d for d in input()]
for i in range(1,W):
 if chk[0][i]==".":
  ans[0][i]=ans[0][i-1]
for i in range(1,H):
 if chk[i][0]==".":
  ans[i][0]=ans[i-1][0]
for i in range(1,H):
 for j in range(1,W):
  if chk[i][j]==".":
   ans[i][j]=ans[i-1][j]+ans[i][j-1]
   ans[i][j]%=mod
print(ans[H-1][W-1])

Solution (Python):
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
a = [input()[:-1] for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(H):
    for j in range(W):
        if a[i][j]=='
            continue
        
        if i-1>=0:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= MOD
        
        if j-1>=0:
            dp[i][j] += dp[i][j-1]
            dp[i][j] %= MOD

print(dp[H-1][W-1])

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	rows, cols = rli()
	dp = [[0 for __ in range(cols)] for _ in range(rows)]
	A = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "
				row.append(1)
			else:
				row.append(0)
		A.append(row)

	dp[0][0] = 1
	for c in range(1, cols):
		if A[0][c] == 1:continue
		dp[0][c] = dp[0][c-1]

	for r in range(1, rows):
		if A[r][0] == 1: continue
		dp[r][0] = dp[r-1][0]

	for r in range(1, rows):
		for c in range(1, cols):
			if A[r][c] == 1: continue
			dp[r][c] = dp[r-1][c] + dp[r][c-1]

	print(dp[-1][-1] % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
mod=round(1e9+7)

r,c = list(map(int, input().split()))
mat = []
for i in range(r):
    mat.append(list(input()))
dp=[]
for i in range(r):
    dp.append([0]*(c))
for i in range(r):
    if mat[i][0]=='
        break
    else:
        dp[i][0]=1
for i in range(c):
    if mat[0][i]=='
        break
    else:
        dp[0][i]=1
for i in range(1,r):
    for j in range(1,c):
        if mat[i][j]=='
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[r-1][c-1])

Solution (Python):
h, w = map(int, input().split())
Mod = 10**9 + 7
a = [["
for i in range(h):
    a.append(["
    a[i+1]+=input()
a[1][1] = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] =="
            continue
        elif i==j==1:
            a[i][j] = 1
            continue
        elif a[i-1][j]=="
            a[i][j] = 0
            continue
        elif a[i-1][j] =="
            a[i][j] = a[i][j-1]
            continue
        elif a[i][j-1] == "
            a[i][j] = a[i-1][j]
            continue
        else:
            a[i][j] = a[i-1][j] + a[i][j-1]
            continue
print(a[h][w]%Mod)

Solution (Python):
H, W = map(int, input().split())

a = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]




dp[0][0] = 1

for i in range(H): 
    for j in range(W): 
        if a[i][j] == "
            continue

        if i == H-1:
            if a[i][j+1] != "
                dp[i][j+1] += dp[i][j]
        elif j == W-1:
            if a[i+1][j] != "
                dp[i+1][j] += dp[i][j]
        else:
            if a[i][j+1] != "
                dp[i][j+1] += dp[i][j]
            if a[i+1][j] != "
                dp[i+1][j] += dp[i][j]

print(dp[-1][-1]%1000000007)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

h,w=map(int,input().split())
a=[input() for i in range(h)]

itta=[[0]*w for i in range(h)]
itta[0][0]=1
d=deque([[0,0]])
while d:
    nh,nw=d.popleft()
    itta[nh][nw]%=mod
    if nh+1<h and a[nh+1][nw]==".":
        if itta[nh+1][nw]==0:
            d.append([nh+1,nw])
        itta[nh+1][nw]+=itta[nh][nw]
    if nw+1<w and a[nh][nw+1]==".":
        if itta[nh][nw+1]==0:
            d.append([nh,nw+1])
        itta[nh][nw+1]+=itta[nh][nw]

print(itta[-1][-1]%mod)

Solution (Python):
n,m=map(int,input().split())
s=[]
dp=[]
mod=10**9+7
for _ in range(n):
    s.append(input())
    dp.append([0]*m)

for i in range(n):
    for j in range(m):
        if i==0 and j==0:
            dp[i][j]=1 
        else:
            if s[i][j]=='
                dp[i][j]=0
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[n-1][m-1])