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):
from collections import*
mod=10**9+7
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dx=[0,1]
dy=[1,0]
d=[[0]*w for _ in range(h)]
v=[[0]*w for _ in range(h)]
d[0][0]=1
q=deque([(0,0)])
while q:
  x,y=q.popleft()
  if v[x][y]:continue
  v[x][y]=1
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if 0<=nx<h and 0<=ny<w and a[nx][ny]==".":
      d[nx][ny]+=d[x][y]
      d[nx][ny]%=mod
      q.append((nx,ny))
print(d[-1][-1])

Solution (Python):
mod = 10**9+7
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
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 maze[i+1][j]==".":
            dp[i+1][j] += dp[i][j]%mod
        if j+1<W and maze[i][j+1]==".":
            dp[i][j+1] += dp[i][j]%mod
            
print(dp[H-1][W-1]%mod)

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

grid = [input() for _ in range(h)]

dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = 1

for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            if y > 0:
                dp[y][x] += dp[y-1][x]
            if x > 0:
                dp[y][x] += dp[y][x-1]

            dp[y][x] %= m

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

Solution (Python):

H, W = map(int, input().split())
grid = []
d = [(1, 0), (0, 1)]
for _ in range(H):
    grid.append(input())
dp = [[0 for _ in range(W)] for _ in range(H)]
mod = 1e9 + 7
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if h > 0 and grid[h - 1][w] == '.':
            dp[h][w] = (dp[h][w] + dp[h - 1][w]) % mod
        if w > 0 and grid[h][w - 1] == '.':
            dp[h][w] = (dp[h][w] + dp[h][w - 1]) % mod
print(int(dp[H - 1][W - 1]))

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

A_map = []
for i in range(H):
    A_str = input()
    A_map.append(A_str)

MOD = 10**9 + 7

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

for i in range(H):
    for j in range(W):
        if A_map[i][j] == '
            continue
        for k in dire:
            if 0 <= i+k[0] <= H-1 and  0 <= j+k[1] <= W-1:
                if A_map[i+k[0]][j+k[1]] == '.':
                    dp[i+k[0]][j+k[1]] +=  dp[i][j]%MOD
                    dp[i+k[0]][j+k[1]] %= MOD

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

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    mod = 10**9 + 7
    h, w = map(int, input().split())

    dp = [0] * (w + 1)
    dp[1] = 1
    for _ in range(h):
        a = input()
        for i in range(w):
            if a[i] == '
                dp[i+1] = 0
            else:
                dp[i+1] += dp[i]
                dp[i+1] %= mod

    print(dp[w])

main()

Solution (Python):





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

def mod(num):
    return num % (10 ** 9 + 7)
    
dp = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[i][j] = 1
            continue

        if A[i][j] == "
            continue

        if i == 0:
            dp[i][j] = dp[i][j - 1]
        elif j == 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = mod(dp[i - 1][j] + dp[i][j - 1])
            
print(dp[-1][-1])

Solution (Python):
''' ===============================
	-- @uthor : Kaleab Asfaw
	-- Handle : kaleabasfaw2010
	-- Bio    : High-School Student
	==============================='''


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
	newlines = 0
	def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b: break
			ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0; return self.buffer.read()
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1; return self.buffer.readline()
	def flush(self):
		if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
	def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")



mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, m, grid):
	dp = arr2D(n, m)
	dp[0][0] = 1
	for i in range(n):
		for j in range(m):
			if grid[i][j] == "." and ((i > 0 and grid[i-1][j] == ".") or (j > 0 and grid[i][j-1] == ".")):
				dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
	return dp[n-1][m-1]

n, m = list(map(int, input().split()))
grid = []
for i in range(n):
	grid.append(input())
print(solve(n, m, grid))

Solution (Python):
def getval():
    h,w = map(int,input().split())
    a = [input() for i in range(h)]
    return h,w,a 

def main(h,w,a):
    mod = 10**9 + 7
    dp = [[0 for i in range(w+1)] for i in range(h+1)]
    dp[1][1] = 1
    for i in range(1,h+1):
        for j in range(1,w+1):
            if i==1 and j==1:
                continue
            if a[i-1][j-1]=="
                continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[h][w])

if __name__=="__main__":
    h,w,a = getval()
    main(h,w,a)

Solution (Python):
def getval():
    h,w = map(int,input().split())
    a = [input() for i in range(h)]
    return h,w,a 

def main(h,w,a):
    mod = 10**9 + 7
    dp = [[0 for i in range(w+1)] for i in range(h+1)]
    dp[1][1] = 1
    for i in range(1,h+1):
        for j in range(1,w+1):
            if i==1 and j==1:
                continue
            if a[i-1][j-1]=="
                continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[h][w])

if __name__=="__main__":
    h,w,a = getval()
    main(h,w,a)

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

Solution (Python):
import sys
import math



def input():
    return sys.stdin.readline().rstrip()


def main():
    H,W =map(int,input().split())
    A =[]
    mod =10**9+7
    for i in range(H):
        a =list(input())
        A.append(a)

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

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





if __name__ == "__main__":
    main()

Solution (Python):
MOD = 10**9 + 7
H, W = map(int, input().split())
maze = []
for _ in range(H):
  maze.append(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 >= 0 and maze[i][j] == ".":
      dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
    if j-1 >= 0 and maze[i][j] == ".":
      dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD
print(dp[H-1][W-1])

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]




H, W = li()
maze = [list(input()) for _ in range(H)]
dp = [[0] * W for _ in range(H)]

dp[0][0] = 1

for y in range(H):
    for x in range(W):
        if maze[y][x] == '
            continue
        if y > 0:
            dp[y][x] += dp[y-1][x]
        if x > 0:
            dp[y][x] += dp[y][x-1]
        dp[y][x] %= MOD

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

Solution (Python):
MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]

dp = [[0] * W for _ in range(H)]
for i in range(H):
    if G[i][0] == '
        break
    dp[i][0] = 1
for i in range(W):
    if G[0][i] == '
        break
    dp[0][i] = 1


for i in range(1, H):
    for j in range(1, W):
        if G[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):
from collections import deque

MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]


def main():
    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if G[i][0] == '
            break
        dp[i][0] = 1
    for i in range(W):
        if G[0][i] == '
            break
        dp[0][i] = 1

    que = deque([(0, 0)])

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (0, 1)):
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '
                continue
            if nh > 0 and nw > 0:
                if dp[nh][nw]:
                    continue
                dp[nh][nw] = (dp[nh - 1][nw] + dp[nh][nw - 1]) % MOD
            que.append((nh, nw))

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]


def main():
    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 0

    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if G[i][0] == '
            break
        dp[i][0] = 1
    for i in range(W):
        if G[0][i] == '
            break
        dp[0][i] = 1

    que = deque([(0, 0)])

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (0, 1)):
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '
                continue
            if dist[nh][nw] != -1:
                continue
            if nh > 0 and nw > 0:
                dp[nh][nw] = (dp[nh - 1][nw] + dp[nh][nw - 1]) % MOD
            dist[nh][nw] = dist[h][w] + 1
            que.append((nh, nw))

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


if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
a = [input() for _ in range(H)]

MOD = 10**9+7

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

for i in range(H):
    if a[i][0] == '.':
        dp[i][0] = 1
    else :
        break

for j in range(W):
    if a[0][j] == '.':
        dp[0][j] = 1
    else :
        break

for i in range(H):
    for j in range(W):
        if i != 0  or j != 0:
            if a[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 = map(int,input().split())
l = [['
for i in range(h):
    l.append(['
l.append(['

mod = 10**9+7
dp = [[0]*(w+2) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            dp[1][1] = 1
            continue
        if l[i][j] == '.':
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod
print(dp[h][w])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



mod = 10**9 + 7

H, W = inpl()
a = []
for i in range(H):
    a.append(input().strip())

dp = [[0] * (W+1) for i in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if a[i][j] == "
            continue
        for x, y in ((1, 0), (0, 1)):
            dp[i+x][j+y] += dp[i][j]
            dp[i+x][j+y] %= mod

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



mod = 10**9 + 7

H, W = inpl()
a = []
flag = [[False] * W for i in range(H)]
for i in range(H):
    a.append(input().strip())
_debug(a)
dp = [[0] * (W+1) for i in range(H+1)]
dp[0][0] = 1

for i in range(max(H, W)):
    if i < H:
        for j in range(W):
            if a[i][j] == "
                continue
            flag[i][j] = True
            for x, y in ((0, 1), (1, 0)):
                dp[i+x][j+y] += dp[i][j]
                dp[i+x][j+y] %= mod
    if i < W:
        for j in range(H):
            if a[j][i] == "
                continue
            flag[j][i] = True
            for x, y in ((0, 1), (1, 0)):
                dp[j+x][i+y] += dp[j][i]
                dp[j+x][i+y] %= mod
    
print(dp[H-1][W-1])

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

H,W = map(int,readline().split())
G = [readline().rstrip() for i in range(H)]
DIV = 10 ** 9 + 7

dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][1] = 1
for i in range(H):
  for j in range(W):
    if G[i][j] == "
      dp[i + 1][j + 1] = 0
      continue
    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
    dp[i + 1][j + 1] %= DIV
    
print(dp[-1][-1])

Solution (Python):
H, W = map(int, input().split())
S = [[a for a in input()] for _ in range(H)]
mod = 10 ** 9 + 7
DP = [[0] * (W + 1) for _ in range(H+1)]
DP[1][1] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i-1][j-1] == '
            continue
        if i == 1 and j == 1:
            continue
        DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
        DP[i][j] %= mod

print(DP[-1][-1])

Solution (Python):
mod = 10 ** 9 + 7
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(input())
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 1
for i in range(H):
  for j in range(W):
    if i == 0:
      if j == 0:
        continue
      else:
        if S[i][j] == ".":
          dp[i][j] = dp[i][j-1]
    else:
      if S[i][j] == ".":
        if j == 0:
          dp[i][j] = dp[i-1][j]
        else:
          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())
dp = [[0]*(W+1) for _ in range(H+1)]
Map = []
for _ in range(H):
    line = list(input())
    Map.append(line)
MOD = 10**9+7
dp[1][1]=1
for i in range(H):
    for j in range(W):
        if Map[i][j]=='
                dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD
            
            dp[i+1][j+1]+=(dp[i][j+1]+dp[i+1][j])%MOD
print(dp[-1][-1])

Solution (Python):
H, W = map(int, input().strip().split())
grid = [list(input()) for i in range(H)]
dp = [[0 for i in range(W+1)] for i in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i][j+1] += dp[i][j]
        dp[i][j] = dp[i][j]%(1000000007)
print(dp[H-1][W-1])

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

Solution (Python):
from sys import stdin 
import math 

def main():

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

	grid = []

	for ind in range(h):
		grid.append(input())


	L = [ [0 for _ in range(w)] for _ in range(h) ]

	L[0][0] = 1

	for h_ind in range(h):
		for w_ind in range(w):
			if grid[h_ind][w_ind] == '.':
				if h_ind - 1 >= 0:
					L[h_ind][w_ind] += L[h_ind - 1][w_ind]
				if w_ind - 1 >= 0:
					L[h_ind][w_ind] +=  L[h_ind][w_ind - 1]


	modulo = int (pow(10, 9) + 7)
	print(L[h - 1][w - 1] % modulo)











if __name__ == '__main__':
	main()

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

def main():
    MOD = 10 ** 9 + 7
    h, w = map(int, input().split())
    tizu = [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 tizu[i][j] == "
                continue
            if i != 0:
                dp[i][j] += dp[i - 1][j]
            if j != 0:
                dp[i][j] += dp[i][j - 1]
            dp[i][j] %= MOD
    print(dp[-1][-1])
main()

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

field = []

for _ in range(H):
    field.append(input())

dp = [[0 for a in range(W)] for b in range(H)]
dp[0][0] = 1



for h in range(H):
    for w in range(W):
        if field[h][w] == '

        if h-1 >= 0 and field[h-1][w] == ".":
            dp[h][w] += dp[h-1][w]

        if w-1 >= 0 and field[h][w-1] == '.':
            dp[h][w] += dp[h][w-1]

        dp[h][w] %= 1000000007

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

Solution (Python):

H,W = map(int,input().split())
maze = []
for _ in range(H):
    a = list(input())
    maze.append(a)


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



dp[0][0] = 1

for h in range(H):
    for w in range(W):
        
        if (h,w) == (0,0):
            continue
        
        if maze[h][w] == '
            continue
        
        if w > 0:
            dp[h][w] = (dp[h][w] + dp[h][w-1])%(10**9+7)
        
        if h > 0:
            dp[h][w] = (dp[h][w] + dp[h-1][w])%(10**9+7)
print(dp[H-1][W-1])

Solution (Python):
h,w=map(int,input().split())
a=[]
for _ in range(h):
  a.append(list(input()))

dp=[[0 for _ in range(w)] for _ in range(h)]
dp[0][0]=1

MOD=10**9+7
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]
      if dp[i+1][j]>=MOD:
        dp[i+1][j]-=MOD
    if j+1<w and a[i][j+1]==".":
      dp[i][j+1]+=dp[i][j]
      if dp[i][j+1]>=MOD:
        dp[i][j+1]-=MOD

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

Solution (Python):
arr=[] 
n,m=map(int,input().split()) 
dp=[[0 for j in range(m)] for i in range(n)] 
for i in range(n):
	arr.append(input()) 
dp[0][0]=1 
for i in range(1,n):
	if arr[i][0]!='
		dp[i][0]+=dp[i-1][0]
	else:
		break  
for i in range(1,m):
	if arr[0][i]!='
		dp[0][i]+=dp[0][i-1]
	else:
		break 


for i in range(1,n):
	for j in range(1,m):
		if arr[i][j]!='
			dp[i][j]=dp[i-1][j]+dp[i][j-1]  
mod=10**9+7 
print(dp[-1][-1]%mod)

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

s=[input() for _ in range(h)]

ans=[[0]*w for _ in range(h)]
for i in range(w):
    if s[0][i]=='
        break
    ans[0][i]=1
for j in range(h):
    if s[j][0]=='
        break
    ans[j][0]=1

for i in range(1,h):
    for j in range(1,w):
        if s[i][j]=='
            ans[i][j]=0
        else:
            ans[i][j]=ans[i][j-1]+ans[i-1][j]

print(ans[h-1][w-1]%(1000000000+7))

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
h,w = ip()
grid = [input().strip() for i in range(h)]
dp = [[0]*w for i in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i-1 >= 0 and grid[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if j-1 >= 0 and grid[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]
        dp[i][j] %= M
print(dp[-1][-1]%M)

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
h,w = ip()
grid = [input().strip() for i in range(h)]
dp = [[0]*w for i in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i-1 >= 0 and grid[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if j-1 >= 0 and grid[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]
print(dp[-1][-1]%M)

Solution (Python):
H, W = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1

mod = 10**9+7

for w in range(1, W):
    if a[0][w]=='
    dp[0][w] = 1
for h in range(1, H):
    if a[h][0]=='
    dp[h][0] = 1
for h in range(1, H):
    for w in range(1, W):
        if a[h][w]=='
        dp[h][w] = (dp[h-1][w]+dp[h][w-1])%mod
print(dp[-1][-1])

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

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


def main():
    
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dp = [[0]*W for i in range(H)]

    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            le = 0
            up = 0
            if 0 <= w - 1 and c[h][w-1] != "
                le = dp[h][w-1]
            if 0 <= h - 1 and c[h-1][w] != "
                up = dp[h-1][w]
            dp[h][w] += le + up
            dp[h][w] %= MOD
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

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


def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dist = [[-1]*W for i in range(H)]

    def bfs_2d(sy=0, sx=0):
        que = deque()

        dist[sy][sx] = 1
        que.append((sy, sx))
        d = ((0, 1), (1, 0))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    dist[next_h][next_w] += dist[uh][uw]
                    dist[next_h][next_w] %= MOD
                    continue
                if c[next_h][next_w] == '
                    continue
                dist[next_h][next_w] = dist[uh][uw]
                dist[next_h][next_w] %= MOD
                que.append((next_h, next_w))

    bfs_2d()
    print(dist[H-1][W-1] if dist[H-1][W-1] != -1 else 0)


if __name__ == '__main__':
    main()

Solution (Python):
INF = 10 ** 9 + 7
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 + 1 < H and a[i + 1][j] == '.':
            dp[i + 1][j] = dp[i][j] + dp[i + 1][j]
            dp[i + 1][j] %= INF
        if j + 1 < W and a[i][j + 1] == '.':
            dp[i][j + 1] = dp[i][j + 1] + dp[i][j]
            dp[i][j + 1] %= INF

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

Solution (Python):
INF = 10 ** 9 + 7
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 + 1 < H and a[i + 1][j] == '.':
            dp[i + 1][j] = dp[i][j] + dp[i + 1][j]
            dp[i + 1][j] %= INF
        if j + 1 < W and a[i][j + 1] == '.':
            dp[i][j + 1] = dp[i][j + 1] + dp[i][j]
            dp[i][j + 1] %= INF

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

Solution (Python):
INF=float('inf')
mod=10**9+7

h,w=map(int,input().split())
G=[]
for _ in range(h):
  s=input()
  G.append(s)
  
dp=[[-INF for i in range(w+1)] for j in range(h+1)]
dp[1][1]=1

for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i-1][j-1]=='
      continue
    if i==1 and j==1:
      continue
    dp[i][j]=max(0,dp[i-1][j])+max(0,dp[i][j-1])
    dp[i][j]%=mod
print(dp[h][w])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp,visited
    if visited[y][x]:
        return dp[y][x]
    else:
        visited[y][x]=True
        if mp[y][x]!='
            dp[y][x]=(grid(y-1,x)+grid(y,x-1))%mod
        return dp[y][x]

H,W=map(int,input().split())
mp=[['
for _ in range(H):
    mp.append(['

dp=[[0]*(W+1)for _ in range(H+1)]
dp[1][1]=1
visited=[[False]*(W+1)for _ in range(H+1)]
mod=10**9+7
grid(H,W)
print(dp[H][W])

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

def grid(y,x,mp):
    mod=10**9+7
    dp=[[0]*x for _ in range(y)]
    dp[0][0]=1
    for h in range(y):
        for w in range(x):
            if mp[h][w]=='.':
                if 1<=h<y and 1<=w<x:
                    dp[h][w]=((dp[h][w-1]+dp[h-1][w])%mod)
                elif h==0 and 1<=w<x:
                    dp[h][w]=(dp[h][w-1]%mod)
                elif 1<=h<y and w==0:
                    dp[h][w]=(dp[h-1][w]%mod)
    return dp[y-1][x-1]


H,W=map(int,input().split())
mp=[list(input()) for _ in range(H)]
print(grid(H,W,mp))

Solution (Python):
def solve(H, W, a):
    mod = 10 ** 9 + 7

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

    for i in range(H):
        for j in range(W):
            if a[i][j] == '.':
                if i == 0 and j == 0:
                    continue
                if i == 0:
                    dp[i][j] = dp[i][j-1]
                    dp[i][j] %= mod
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                    dp[i][j] %= mod

    return dp[H-1][W-1]


if __name__ == "__main__":
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]

    print(solve(H, W, a))

Solution (Python):
def grid(maze,h,w):
    mod = 7+10**9
    visited = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "
                continue

            if i==0 and j==0:
                visited[i][j] = 1
                
            
            elif i == 0:
                visited[i][j] = visited[i][j-1]
            elif j == 0:
                visited[i][j] = visited[i-1][j]
            else:
                visited[i][j] = (visited[i-1][j]%mod + visited[i][j-1]%mod)%mod
    
    return visited[h-1][w-1]


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

maze = []

for _ in range(h):
    maze.append(list(input()))

print(grid(maze,h,w))