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):
H, W = map(int, input().split())

A = ['' for i in range(H)]
dp = [[1 for i in range(W)] for j in range(H)]

for i in range(H):
  A[i] = input()

for i in range(0, H):
  for j in range(0, W):
    if i+j == 0:
      continue
    if A[i][j] == '
      dp[i][j] = 0
    else:
      if (A[i-1][j] == '
      else: x = dp[i-1][j]
      if (A[i][j-1] == '
      else: y = dp[i][j-1] 
      dp[i][j] = x+y

print(dp[-1][-1] % (10**9+7))

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

grid = []

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

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

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if grid[i][j] != "
            if i-1 >= 0:
                dp[i][j] += dp[i-1][j]
            if j-1 >= 0:
                dp[i][j] += dp[i][j-1]
mod = 1000000007
print(dp[-1][-1] % mod)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


H, W = na()

A_array = [ns() for _ in range(H)]

mod = 10 ** 9 + 7

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

ans[0][0] = 1
for i in range(1, W):
    if A_array[0][i] == "
        continue
    ans[0][i] = ans[0][i-1]

for i in range(1, H):
    if A_array[i][0] == "
        continue
    ans[i][0] = ans[i-1][0]


for i in range(1, H):
    for j in range(1, W):
        if A_array[i][j] == "
            continue
        ans[i][j] = (ans[i-1][j] + ans[i][j-1]) % mod

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

Solution (Python):
import sys
from collections import deque
def main():
    MOD=10**9+7
    q=deque()
    H,W=tuple(map(int,sys.stdin.readline().split()))
    m,dp=[],[[0 for _ in range(W)] for _ in range(H)]
    for _ in range(H):m.append(list(sys.stdin.readline().strip()))
    dp[0][0]=1
    q.append((0,0))
    while len(q)>0:
        h,w=q.popleft()
        if h+1<H and m[h+1][w]=='.':  
            if dp[h+1][w]==0:q.append((h+1,w))
            dp[h+1][w]=(dp[h+1][w]+dp[h][w])%MOD
        if w+1<W and m[h][w+1]=='.':  
            if dp[h][w+1]==0:q.append((h,w+1))
            dp[h][w+1]=(dp[h][w+1]+dp[h][w])%MOD
    print(dp[H-1][W-1])
if __name__=='__main__':main()

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

Solution (Python):
import sys
from collections import deque
def main():
    MOD=10**9+7
    q=deque()
    H,W=tuple(map(int,sys.stdin.readline().split()))
    m=[]
    for _ in range(H):
        m.append(list(sys.stdin.readline().strip()))
    dp=[[0 for _ in range(W)] for _ in range(H)]
    dp[0][0]=1
    q.append((0,0))
    while len(q)>0:
        h,w=q.popleft()
        if h+1<H and m[h+1][w]=='.':  
            if dp[h+1][w]==0:q.append((h+1,w))
            dp[h+1][w]=(dp[h+1][w]+dp[h][w])%MOD
        if w+1<W and m[h][w+1]=='.':  
            if dp[h][w+1]==0:q.append((h,w+1))
            dp[h][w+1]=(dp[h][w+1]+dp[h][w])%MOD
    print(dp[H-1][W-1])
if __name__=='__main__':main()

Solution (Python):
import queue
INF=10**8
R=10**9+7
h,w=map(int,input().split())
maze=[input() for _ in range(h)]
d=[[0 for i in range(h)] for _ in range(w)]
sx=0
sy=0
gx=w-1
gy=h-1
q=queue.Queue()
dx=[1,0]
dy=[0,1]
q.put((sx,sy))
d[sy][sx]=1
while not q.empty():
  x,y=q.get()
  if (x,y)==(gx,gy):break
  for i in range(2):
    nx=x+dx[i]
    ny=y+dy[i]
    if nx<w and ny<h:
      if maze[ny][nx]=='.':
        if d[nx][ny]==0:
          q.put((nx,ny))
          d[nx][ny]=d[x][y]
        else:d[nx][ny]+=d[x][y]
print(d[gx][gy]%R)

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x)


def solve(H, W, data):
    "void()"
    score = [[0] * (W + 1) for i in range(H + 1)]
    score[0][1] = 1
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            if data[y - 1][x - 1] == ord("
                score[y][x] = 0
            else:
                score[y][x] = (score[y - 1][x] + score[y][x - 1]) % MOD
    
    return score[H][W]


def main():
    H, W = map(int, input().split())
    data = [input() for i in range(H)]
    print(solve(H, W, data))


T1 = """
3 4
...
.
....
"""

T2 = """
5 5
..
.....

.....
..
"""

T3 = """
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
"""

T4 = """
5 2
..

..
.
..
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    """


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    345263555
    """


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    24
    """


def _test():
    """
    >>> as_input(T1)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
MOD = 10**9+7
H, W = map(int, input().split())
a = [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 j+1 < W:
            if a[i][j+1] != '
                dp[i][j+1] += dp[i][j] % MOD
        if i+1 < H:
            if a[i+1][j] != '
                dp[i+1][j] += dp[i][j] % MOD
            
print(dp[H-1][W-1] % MOD)

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

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

H,W = map(int,readline().split())
G = [None] * (H + 1)
G[0] = "." * (W + 1)
for i in range(H):
  G[i + 1] = "." + readline().rstrip()

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

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

Solution (Python):
import numpy as np

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

dp = np.zeros((h, w), dtype = np.int64)
dp[0][0] = 1
mod = 10**9 + 7

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			if j == 0:
				if i == 0:
					continue
				dp[i][j] = dp[i-1][j]
			else:
				if i == 0:
					dp[i][j] = dp[i][j-1]
				else:
					dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
print(dp[h-1][w-1])

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

Solution (Python):
n = input().split()
r = int(n[0])
c = int(n[1])

a = []
MOD = 10**9+7

for i in range(r):
    x = input()
    y = []
    for char in x:
        if char == '.':
            y.append(1)
        else:
            y.append(0)
    a.append(y)

if a:
    dp = [[0 for i in range(c)] for j in range(r)]

    dp[0][0] = a[0][0]

    for i in range(1,r):
        dp[i][0] = dp[i-1][0] * a[i-1][0]

    for j in range(1,c):
        dp[0][j] = dp[0][j-1] * a[0][j-1]

    for i in range(1,r):
        for j in range(1,c):
            dp[i][j] = dp[i-1][j] * a[i-1][j] + dp[i][j-1] * a[i][j-1]

print((dp[r-1][c-1] * a[r-1][c-1])%MOD)

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

grid = [None] * H

for i in range(H):
    grid[i] = input()

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

dp[1][1] = 1
M = 10 ** 9 + 7

for L in range(1,H + 1):
    for C in range(1,W + 1):
        if L == 1 and C == 1:
            continue
        else:
            if grid[L-1][C-1] == ".":
                dp[L][C] = dp[L][C-1] + dp[L-1][C]
                dp[L][C] %= M

print(dp[H][W])

Solution (Python):
h, w = map(int, input().split())
m = [['
for j in range(h):
    m[j+1][1:w+1] = list(input()) 

dp = [[0 for i in range(w+2)] for j in range(h+2)]

dp[1][1] = 1

for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if m[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]

print(dp[h][w] % 1000000007)

Solution (Python):
def main():
    m = 1000000007

    h, w = map(lambda x: int(x), input().split())

    grid = []
    for row in range(h):
        grid.append(input())

    count = []
    for row in range(h):
        count.append([0] * w)

    for row in range(h):
        if grid[row][0] == "
            break
        count[row][0] = 1

    for column in range(w):
        if grid[0][column] == "
            break
        count[0][column] = 1

    for row in range(1, h):
        for column in range(1, w):
            if grid[row][column] == ".":
                count[row][column] = (
                    (count[row - 1][column] % m) +
                    (count[row][column - 1] % m)
                ) % m

    print(count[-1][-1])

main()

Solution (Python):
def main():
    m = 1000000007

    h, w = map(lambda x: int(x), input().split())

    grid = []
    for row in range(h):
        grid.append(input())

    count = []
    for row in range(h):
        count.append([0] * w)

    for row in range(h):
        if grid[row][0] == "
            break
        count[row][0] = 1

    for column in range(w):
        if grid[0][column] == "
            break
        count[0][column] = 1

    for row in range(1, h):
        for column in range(1, w):
            if grid[row][column] == ".":
                count[row][column] = (
                    (count[row - 1][column] % m) +
                    (count[row][column - 1] % m)
                ) % m

    print(count[-1][-1])

main()

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

grid = []

for i in range(h):
    row = list(input()) 

    for i in range(len(row)):
        if row[i] == '.':
            row[i] = 0
    
    grid.append(row)

num = 1000000007

for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == '
            continue
        if i == 0 and j == 0:
            grid[i][j] = 1
        elif i == 0:
            if grid[i][j-1] != '
                grid[i][j] = grid[i][j-1] % num
        elif j == 0:
            if grid[i-1][j] != '
                grid[i][j] = grid[i-1][j] % num
        else:
            if grid[i][j-1] == '
                grid[i][j] = 0
            elif grid[i][j-1] == '
                grid[i][j] = grid[i-1][j] % num
            elif grid[i-1][j] == '
                grid[i][j] = grid[i][j-1] % num
            else:
                grid[i][j] = (grid[i-1][j] + grid[i][j-1]) % num

print(grid[-1][-1])

Solution (Python):
x, y = map(int, input().split())
grid = []
visit = []
mod = 1000000007
for _ in range(x):
    grid.append([i for i in input()])
    visit.append([0 for i in range(y)])
grid[x-1][y-1] = 'X'
visit[x-1][y-1] = 1
for i in range(x-1, -1, -1):
    for j in range(y-1, -1, -1):
        if grid[i][j] == '.':
            if i < x-1 and j < y-1:
                visit[i][j] = (visit[i][j+1] + visit[i+1][j])%mod
            elif i < x-1 and j == y-1:
                visit[i][j] = visit[i+1][j]
            else:
                visit[i][j] = visit[i][j+1]
print(visit[0][0])

Solution (Python):
h, w = map(int, input().split())
a = [["
for _ in range(h):
    a.append(["
mod = 10 ** 9 + 7

dp = [[0] * (w + 1) for _ in range(h + 1)]
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        if hi == 1 and wi == 1:
            dp[hi][wi] = 1
            continue
        if a[hi][wi] == ".":
            dp[hi][wi] = dp[hi-1][wi] + dp[hi][wi-1]
            dp[hi][wi] %= mod

ans = dp[h][w]
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1
M = 10**9+7
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]==".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= M
print(dp[h][w])

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

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] == '
            continue
        if i + 1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= 1e9 + 7
        if j + 1 < W and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= 1e9 + 7
        
print(int(dp[-1][-1]))

Solution (Python):


LI = lambda: list(map(int, input().split()))


H, W = LI()
A = [input() for _ in range(H)]

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if A[i][0] == "
            break
        dp[i][0] = 1
    for j in range(W):
        if A[0][j] == "
            break
        dp[0][j] = 1
    for i in range(1, H):
        for j in range(1, W):
            if A[i - 1][j] == ".":
                dp[i][j] = dp[i - 1][j]
            if A[i][j - 1] == ".":
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD
    ans = dp[-1][-1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
MOD = 1000000007
H, W = (int(x) for x in input().split())
grid = []
for row in range(H):
  grid.append(input())

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

if grid[H-1][W-1] == '
  print(0)
else:
  dp[H-1][W-1] = 1

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

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

Solution (Python):

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

m = 1000000007

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for w in range(1, W):
    if a[0][w] != '
        dp[0][w] = dp[0][w - 1]

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

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

Solution (Python):

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

m = 1000000007

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for h in range(H - 1):
    for w in range(W - 1):
        if a[h][w] == '
            continue
        if a[h][w + 1] != '
            dp[h][w + 1] = (dp[h][w + 1] + dp[h][w]) % m
        if a[h + 1][w] != '
            dp[h + 1][w] = (dp[h + 1][w] + dp[h][w]) % m
    if a[h][W - 1] == '
        continue
    if a[h + 1][W - 1] != '
        dp[h + 1][W - 1] = (dp[h + 1][W - 1] + dp[h][W - 1]) % m
for w in range(W - 1):
    if a[H - 1][w] == '
        continue
    if a[H - 1][w + 1] != '
        dp[H - 1][w + 1] = (dp[H - 1][w + 1] + dp[H - 1][w]) % m

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

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

dp=[[0 for i in range(w+1)] for i in range(h+1)]
dp[h-1][w-1]=1
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if li[i][j]=='
            dp[i][j]=0
        else:
            if i==(h-1) and j==(w-1):
                dp[i][j]=1
            else:
                dp[i][j]=dp[i+1][j]+dp[i][j+1]
print(dp[0][0]%(10**9+7))

Solution (Python):
mod=1000000007
h,w=map(int,input().split())
grid=[]
for _ in range(h):
    s=list(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 grid[i][j]=='
            continue
        if i>0:
            dp[i][j]+=dp[i-1][j]%mod
        
        if j>0:
            dp[i][j]+=dp[i][j-1]%mod
        
print(dp[h-1][w-1]%mod)

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal











 



 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 
 

def pr_list(a):
	print(*a, sep=" ")
def main():
	
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	m = [0,-1]
	for test in range(tests):
		[n,m] = inlt()
		grid = []
		for i in range(n):
			grid.append(insr())
		dp = [[0 for j in range(m)] for i in range(n)]
		dp[-1][-1] = 1
		move = {}
		move[(n-1,m-1)] =1
		while(move != {}):
			n_move = {}
			
			for i in move:
				
				if i[0]-1 >=0 and grid[i[0]-1][i[1]] == ".":
					dp[i[0]-1][i[1]] = (dp[i[0]-1][i[1]]+ dp[i[0]][i[1]])%mod
					n_move[ (i[0]-1,i[1]) ] =1
				if i[1]-1 >=0 and grid[i[0]][i[1]-1]  == "." :
					dp[i[0]][i[1]-1] = (dp[i[0]][i[1]-1]+ dp[i[0]][i[1]])%mod
					n_move[ (i[0],i[1]-1) ] =1
			move = n_move
		print(dp[0][0])


if __name__== "__main__":
	main()

Solution (Python):
h, w = map(int, input().split())
arr = [list(map(str, input().rstrip())) 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 arr[i - 1][j - 1] == "
            continue
        else:
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1]

print(dp[h][w] % MOD)

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

H,W=map(int,input().split())
a=[list(input()) for _ in range(H)]
a[0][0]=1
for h in range(H):
    for w in range(W):
        if h==0:
            if w==0:
                continue
            if a[h][w]==".":
                a[h][w]=a[h][w-1]
            else:
                a[h][w]=0
        else:
            if a[h][w]=="
                a[h][w]=0
            elif w==0:
                a[h][w]=a[h-1][w]
            else:
                a[h][w]=(a[h-1][w]+a[h][w-1])%mod
print(a[-1][-1])

Solution (Python):
h,w=map(int,input().split())
dp=[ [-1]*(w+1) for _ in range(h+1) ]
for i in range(h):
  i+=1
  tmp=input()
  for j in range(w):
    j+=1
    if tmp[j-1]=='.':
      dp[i][j]=0
    else:
      dp[i][j]=-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 dp[i][j]==-1:continue
    dp[i][j]=0
    if dp[i-1][j]!=-1:
      dp[i][j]+=dp[i-1][j]
    if dp[i][j-1]!=-1:
      dp[i][j]+=dp[i][j-1]
    dp[i][j]=dp[i][j]%(10**9+7)

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

Solution (Python):
h,w=map(int,input().split())
dp=[ [-1]*(w+1) for _ in range(h+1) ]
for i in range(h):
  i+=1
  tmp=input()
  for j in range(w):
    j+=1
    if tmp[j-1]=='.':
      dp[i][j]=0
    else:
      dp[i][j]=-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 dp[i][j]==-1:continue
    dp[i][j]=0
    if dp[i-1][j]!=-1:
      dp[i][j]+=dp[i-1][j]
    if dp[i][j-1]!=-1:
      dp[i][j]+=dp[i][j-1]
    dp[i][j]=dp[i][j]%(10**9+7)

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

Solution (Python):
mod=1e9+7
def addself(a):
    if(a<mod):
        return a
    else:
        return (a+mod)%mod
    
n,m=map(int,input().split())
x = []
dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1][1] = 1
for i in range(n):
    l = list(input())
    x.append(l)
for i in range(1,n+1):
    for j in range(1,m+1):
        if i ==1 and j==1:
            continue
        if x[i-1][j-1]=='
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j]+dp[i][j-1]

        dp[i][j]=addself(dp[i][j])
            
print(int(dp[-1][-1]))

Solution (Python):
MOD = 10**9 + 7
def solve(h, w, a):
    dp = [[0]*(w+1) for y in range(h+1)]
    dp[0][0] = 1
    for y in range(h):
        for x in range(w):
            if a[y][x] == ".":
                dp[y+1][x] = (dp[y+1][x] + dp[y][x]) % MOD
                dp[y][x+1] = (dp[y][x+1] + dp[y][x]) % MOD
    return dp[h-1][w-1]

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

Solution (Python):
h,w=map(int,input().split())
wall=[list(input()) for i in range(h)]
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==0 and j==0:
      continue
    tmp=0
    if i > 0 and wall[i-1][j]=='.':
      tmp+=dp[i-1][j]
    if j > 0 and wall[i][j-1]=='.':
      tmp+=dp[i][j-1]
    dp[i][j]+=tmp
print(dp[h-1][w-1] % 1000000007)

Solution (Python):
md = 1000000007
n,m = map(int,input().split())

grid=[]
for i in range(n):
    grid.append(list(input()))

dp=[]
for i in range(n):
    dp.append([0]*m)
dp[0][0]=1
for i in range(1,n):
    if(grid[i][0]!="
        dp[i][0]=dp[i-1][0]
    else:
        dp[i][0]=0

for j in range(1,m):
    if(grid[0][j]!="
        dp[0][j]=dp[0][j-1]
    else:
        dp[0][j]=0

for i in range(1,n):
    for j in range(1,m):
        if(grid[i][j]=="
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%md
print(dp[n-1][m-1])

Solution (Python):



H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 0
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}
mod = 10**9+7

from collections import deque

def bfs(init):
    next_q = deque([])
    for hi, hw in init:
        next_q.append([hi,hw])
        Dist[hi][hw] = 1

    while len(next_q)!=0:
        
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.':
                if Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                Dist[hs][ws] += Dist[h][w]
                Dist[hs][ws] %= mod
    return Dist

def main():
    ret = bfs([[sth, stw]])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
 
sys.setrecursionlimit(100000)
 
H, W = map(int, input().split())

stage = []
for h in range(H):
    a = list(input())
    stage.append(a)

memo = [[-1 for i in range(W)] for j in range(H)]

def move(x, y):
    if x >= W or y>=  H:
        return 0
    if x == W-1 and y == H-1:
        return 1
    if stage[y][x] == "
        return 0
    if memo[y][x] != -1:
        return memo[y][x]
    p = move(x+1, y)+move(x,y+1)
    memo[y][x] = p
    return p

print(move(0,0)%(10**9+7))

Solution (Python):
h, w = map(int, input().split())
a = list(input() for i in range(h))

dp = list([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(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):
H, W = map(int, input().split(" "))
m = [list(input().strip()) for _ in range(H)]
mod = 10**9 + 7

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

for h in range(H):
    for w in range(W):
        if h+1 < H and m[h+1][w] == ".":
            dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= mod
        if w+1 < W and m[h][w+1] == ".":
            dp[h][w+1] += dp[h][w]
            dp[h][w+1] %= mod

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

Solution (Python):
h,w=map(int,input().split())
mat=[]
for i in range(h):
    a=[i for i in list(input())]
    mat.append(a)
for i in range(w):
    if mat[0][i]=='.':
        mat[0][i]=1
    else:
        for j in range(i,w):
            mat[0][j]=0
        break
for i in range(1,h):
    for j in range(w):
        if mat[i][j]=='.':
            mat[i][j]=0
            mat[i][j]=(mat[i][j]+mat[i-1][j])%1000000007
            if j-1>=0:
                mat[i][j]=(mat[i][j]+mat[i][j-1])%1000000007
        else:
            mat[i][j]=0

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

Solution (Python):
import sys
import math
from  collections import defaultdict





mod = 1000000007

def solve(test):
	h, w = map(int, input().split())
	grid = []
	for i in range(h):
		grid.append(list(input()))


	dp = [[0 for j in range(w)] for i in range(h)]
	dp[0][0] = 1
	for j in range(1, w):
		if grid[0][j] == '.':
			dp[0][j] += dp[0][j - 1]

	for i in range(1, h):
		if grid[i][0] == '.':
			dp[i][0] += dp[i - 1][0]

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

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




if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

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

Solution (Python):
h,w=map(int,input().split())
a=[]
for _ in range(h):
    a.append(list(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]%(10**9+7)
        if j+1<w and a[i][j+1]=='.':
            dp[i][j+1]+=dp[i][j]%(10**9+7)
print(dp[h-1][w-1]%(10**9+7))

Solution (Python):


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

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
















flag= False

for h in range(H-1,-1,-1):
    

    if arr[h][W-1]=='
        dp[h][W-1]=0
        flag =  True
    if flag:
        dp[h][W-1]=0
    else:
        dp[h][W-1]=1

    
flag = False
for w in range(W-1,-1,-1):
    
    if arr[H-1][w]=='
        dp[H-1][w]=0
        flag =  True
    if flag:
        dp[H-1][w]=0
    else:
        dp[H-1][w]=1




MOD = 10**9+7

dp[H-1][W-1]=0

for row in range(H-1,0,-1):
    for col in range(W-1,0,-1):
        if arr[row-1][col-1]=='
            dp[row-1][col-1]=0
        elif dp[row][col-1] ==0 or dp[row-1][col]==0:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
            dp[row-1][col-1]%=MOD

        elif dp[row][col-1] > 0 and dp[row-1][col]>0:
            dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]
            dp[row-1][col-1]%=MOD
        elif  dp[row][col-1] == 0 and dp[row-1][col] == 0:
            dp[row-1][col-1]==0


print(dp[0][0])

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

Solution (Python):
n,m=map(int,input().split())

grid=[]
for i in range(n):
  x=list(input())
  grid.append(x)
  

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

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

grid = []
for _ in range(h):
    temp = list(input())
    grid.append(temp)


dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = 1
MOD = 10**9 + 7

for i in range(h):
    for j in range(w):
        if grid[i][j] == '.':
            if i > 0:
                dp[i][j] += dp[i-1][j] % MOD
            if j > 0:
                dp[i][j] += dp[i][j-1] % MOD

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