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())
dp = [list(input())for i in range(H)]
mod = 10**9+7
'''
dp = [[0]*(W) for i in range(H)]

dp[0][0] = 1
dp[1][0] = 1 if maze[1][0] != '
dp[0][1] = 1 if maze[1][0] != '

for i in range(H):
    for j in range(W):
        if 0 <= i+1 < H and 0 <= j+1 < W and maze[i+1][j] != '
            dp[i+1][j+1] += dp[i+1][j] % mod
        if 0 <= j+1 < W and 0 <= i+1 < H and maze[i][j+1] != '
            dp[i+1][j+1] += dp[i][j+1] % mod
print(dp[H-1][W-1] % mod) if dp[H-1][W-1] != float('inf') else 0
'''
dp[0][0] = 1
'''
dp[0][1] = 1 if dp[0][1] != '
dp[1][0] = 1 if dp[1][0] != '
'''
for i in range(H):
    for j in range(W):
        if dp[i][j] != '
            if isinstance(dp[i][j], int):
                dp[i][j] += dp[i][j-1] % mod
            else:
                dp[i][j] = dp[i][j-1] % mod
        if dp[i][j] != '
            if isinstance(dp[i][j],int):
                dp[i][j] += dp[i-1][j] % mod
            else:
                dp[i][j] = dp[i-1][j] % mod
'''
print(dp)
'''
print(dp[H-1][W-1] % mod) if dp[H-1][W-1] != '.' else print(0)

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

a = [input() for _ in range(h)]
dp=[[0 for i in range(w)] for j in range(h)]
MOD=10**9+7
if a[0][0]==".":
    dp[0][0]=1

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

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

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

a = [input() for _ in range(h)]
dp=[[0 for i in range(w)] for j in range(h)]
MOD=10**9+7
if a[0][0]==".":
    dp[0][0]=1

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

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]*(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 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())
a = [input() for _ in range(h)]
MOD = 10**9+7

dp = [[0]*(w+1) for _ in range(h+1)]
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 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())
p = 10**9+7
S = []
for i in range(h):
    S.append(list(input()))
A = [[0 for j in range(w)] for i in range(h)]
flag = True
for i in range(h):
    if S[i][0] == '
        flag = False
    if flag:
        A[i][0] = 1
flag = True
for j in range(w):
    if S[0][j] == '
        flag = False
    if flag:
        A[0][j] = 1
for i in range(1, h):
    for j in range(1, w):
        if S[i][j] == '
            A[i][j] = 0
        else:
            A[i][j] = (A[i-1][j]+A[i][j-1]) % p
print(A[h-1][w-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
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 S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

H,W = LI()
c = [list(S()) for i in range(H)]
dp = FILL(0,H+1,W+1)
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i+1<H:
            if c[i+1][j] == '.':
                dp[i+1][j] += dp[i][j]

        if j+1<W:
            if c[i][j+1] == '.':
                dp[i][j+1] += dp[i][j]

        dp[i][j] %= MOD


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

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

H, W = map(int, input().split())
dp = []
grid = []

for _ in range(H):
    dp.append([0] * W)
    grid.append(input())

dp[0][0] = 1

for r in range(H):
    for c in range(W):
        if grid[r][c] == "
            continue

        up = dp[r-1][c] if r > 0 else 0
        left = dp[r][c-1] if c > 0 else 0

        dp[r][c] = (up + left) % MOD

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

Solution (Python):
MOD = 10**9 + 7
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[0]*(W) for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for k in range(W):
        if i+1 < H and grid[i+1][k] != '
            dp[i+1][k] += dp[i][k]
        if k+1 < W and grid[i][k+1] != '
            dp[i][k+1] += dp[i][k]
        dp[i][k] %= MOD
print(dp[H-1][W-1]%MOD)

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

Solution (Python):
r, c = map(int, input().split())
mat = [input() for _ in range(r)]
dp = [[0]*c for _ in range(r)]
for i in range(c):
    if mat[0][i] == '
        break
    dp[0][i] = 1
for i in range(r):
    if mat[i][0] == '
        break
    dp[i][0] = 1
for i in range(1, r):
    for j in range(1, c):
        if mat[i][j] != '
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10**9 + 7)
print(dp[-1][-1])

Solution (Python):
h,w=map(int,input().split())
mat=[]
dp=[]
dp.append([0]*(w+1))

for i in range(h):
    l=input()
    mat.append(l)
    dp.append([0]*(w+1))

dp[0][1]=1
for i in range(h):
    for j in range(w):
        if mat[i][j]=='.':
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%1000000007
            

print(dp[h][w])

Solution (Python):
grid = []
dp = []
h,w = [int(x) for x in input().split()]

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

dp[-1][-1] = 1

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if grid[i][j] == '
            continue

        if i+1 < h and grid[i+1][j] != '
            dp[i][j] += dp[i+1][j]
        if j+1 < w and grid[i][j+1] != '
            dp[i][j] += dp[i][j+1]

print(dp[0][0] % int(1e9+7))

Solution (Python):
H,W = [int(v) for v in input().split()]
arr = [input() for _ in range(H)]
     
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[1][1] = 1
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[1][1] = 1
     

for h,row in enumerate(arr,1):
        for w,cell in enumerate(row,1):
            if cell != '
                dp[h][w] += int((dp[h-1][w] + dp[h][w-1]) % (1e9 + 7))
    
print(dp[-1][-1])

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

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

for h,row in enumerate(area,1):
    for w,cell in enumerate(row,1):
        if cell != '
            dp[h][w] += int((dp[h-1][w] + dp[h][w-1]) % (1e9 + 7))

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

Solution (Python):
H, W = map(int,input().split())
Root = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    String = input()
    for j in range(W):
        Root[i][j] = String[j]
if Root[0][0] == '.':
    Grid = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(H):
    for j in range(W):
        if Root[i][j] == '.':
            if i == 0 and j == 0:
                Grid[1][1] = 1
            else:
                Grid[i+1][j+1] = Grid[i+1][j] + Grid[i][j+1]
        else:
            Grid[i+1][j+1] = 0
print(Grid[H][W] % 1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): 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 dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
A = [input() for i in range(H)]

dp = dp2(float("inf"), W, H)
dp[0][0] = 1
INF = 10**9+7

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

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

Solution (Python):
h, w = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    a = input()
    for j, k in enumerate(a):
        if i == 0 and j == 0:
            continue
        if k != "
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[h-1][w-1])

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

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

h,w = map(int,readline().split())
maze = []
for _ in range(h):
	maze.append(readline().rstrip().decode('utf-8'))

dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if maze[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]%=10**9+7

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

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 y in range(0, H):
    for x in range(0, W):
        if A[y][x] == '
            continue

        if x - 1 >= 0:
            dp[y][x] += dp[y][x-1]
            dp[y][x] %= MOD
        if y - 1 >= 0:
            dp[y][x] += dp[y-1][x]
            dp[y][x] %= MOD

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

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

div = 10**9+7

patterns = [[0 for _ in range(W)] for __ in range(H)]
patterns[0][0] = 1


for y in range(H):
    for x in range(W):
        if x + 1 < W and field[y][x+1] != '
            patterns[y][x+1] += patterns[y][x] % div
        if y + 1 < H and field[y+1][x] != '
            patterns[y+1][x] += patterns[y][x] % div

print(patterns[-1][-1] % div)

Solution (Python):




'''
5 2
..

..
.
..
'''


H, W = map(int, input().split())

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

dp[0] = [0] * (W+1)

for i in range(H):
    temp = list(input())
    dp[i + 1][0] = 0
    for j in range(W):
        data[i + 1][j + 1] = temp[j]


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

        if data[i][j] == '.':
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = 0


print(dp[H][W] % (10**9+7))

Solution (Python):
def solve(n, m, grid):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    mod = int(1e9+7)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if grid[i-1][j-1] == '
                continue
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod

    return dp[-1][-1]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    grid = [input() for _ in range(n)]
    print(solve(n, m, grid))


if __name__ == '__main__':
    main()

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

MOD=10**9+7

dp=[[-1]*W for _ in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        if s[j]=='
            dp[i][j]=0
dp[0][0]=1

'''

import numpy as np
dp=np.array([list(input()) for _ in range(H)])

dp=np.where(dp=='.',-1,dp)
dp=np.where(dp=='

dp[0][0]=1
'''
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            elif i>=1 and j==0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j>=1:
                dp[i][j]=dp[i][j-1]

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

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

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

DP[0][0] = 1

mod = 10**9 + 7

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            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[H-1][W-1])

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

dp[-1][-1]=1
for i in range(m-2,-1,-1):
    if l[n-1][i]=='
        pass
    else:
        dp[n-1][i]+=dp[n-1][i+1]
for i in range(n-2,-1,-1):
    if l[i][m-1]=='
        pass
    else:
        dp[i][m-1]+=dp[i+1][m-1]
for i in range(n-2,-1,-1):
    for j in range(m-2,-1,-1):
        if l[i][j]=='
            pass
        else:
            dp[i][j]=(dp[i][j+1]+dp[i+1][j])%e
print(dp[0][0])

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] = int(a[0][0] == '.')

for i in range(1,h):
    dp[i][0] = int(a[i][0] == ".")*dp[i-1][0]
for j in range(1,w):
    dp[0][j] = int(a[0][j] == ".")*dp[0][j-1]

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



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

Solution (Python):
H, W = map(int, input().split())
A = [[1] * (W + 2)]
for _ in range(H):
    tmp = list(input())
    tmp = [1] + [0 if t == '.' else 1 for t in tmp] + [1]
    A.append(tmp)
A += [[1] * (W + 2)]

MOD = 10**9 + 7

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



for i in range(H + 1, 0, -1):
    for j in range(W + 1, 0, -1):
        if A[i][j] == 0:
            dp[i][j] = (dp[i][j] + dp[i + 1][j] + dp[i][j + 1]) % MOD
ans = dp[1][1]
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)

def main():
    H,W = map(int,input().split())
    s = [list(input()) for _ in range(H)]
    MOD = 10**9+7
    
    memo = [[-1 for _ in range(W)] for _ in range(H)]
    memo[0][0] = 1
    def ch(x,y):
        if memo[x][y] != -1:
            return memo[x][y]
        else:
            ret = 0
            if x == 0:
                if s[x][y-1] == ".":
                    ret += ch(x,y-1)
            elif y == 0:
                if s[x-1][y] == ".":
                    ret += ch(x-1,y)
            else:
                if s[x][y-1] == ".":
                    ret += ch(x,y-1)
                if s[x-1][y] == ".":
                    ret += ch(x-1,y)
            ret %= MOD
            memo[x][y] = ret
            return ret
    
    ch(H-1,W-1)
    print(memo[-1][-1]%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

H, W = MAP()
a = ["

dx = [1, 0]
dy = [0, 1]

comb = [[0]*(W+2) for _ in range(H+2)]
comb[1][1] = 1
q = deque()
q.append((1, 1))
while q:
    i, j = q.popleft()
    for k in range(2):
        y = i+dy[k]
        x = j+dx[k]
        if a[y][x] != "
            if comb[y][x] == 0:
                q.append((y, x))
            comb[y][x] = (comb[y][x] + comb[i][j])%mod

print(comb[H][W])

Solution (Python):


H,W=map(int,input().split())

A=[]
for _ in range(H):
    A.append(list(input()))

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

for h in range(H):
    for w in range(W):
        if A[h][w]==".":
            dp[h+1][w+1]+=dp[h][w+1]+dp[h+1][w]
            dp[h+1][w+1]%=(10**9+7)

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

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

H, W = map(int, input().split())
count = [0] * W

row = input()
for w in range(W):
  if row[w] == '
    break
  else:
    count[w] = 1

for h in range(1, H):
  row = input()
  if row[0] == '
    count[0] = 0
  for w in range(1, W):
    if row[w] == '
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])

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

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

for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            dp[h][w] = 1
        elif A[h][w] == "
            dp[h][w] = 0
        elif h == 0:
            dp[h][w] = dp[h][w-1]
        elif w == 0:
            dp[h][w] = dp[h-1][w]
        elif A[h][w] == ".":
            dp[h][w] = dp[h][w-1] + dp[h-1][w]

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

Solution (Python):
from collections import deque

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

d = deque([[0,0]])
n_pattern = [[0]*W for _ in range(H)]
n_pattern[0][0] = 1

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and a[new_y][new_x] == ".":
            if n_pattern[new_y][new_x] > 0:
                once_updated_flg = 1
            else:
                once_updated_flg = 0
            n_pattern[new_y][new_x] += n_pattern[y][x]
            n_pattern[new_y][new_x] %= MOD
            if once_updated_flg == 0:
                d.append([new_y, new_x])

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

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

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

dp = [[0]*w for i in range(h)]
dp[0][0] = 1
for i in range(1,w):
    if a[0][i] == '
    dp[0][i] = 1
for i in range(1,h):
    if a[i][0] == '
    dp[i][0] = 1

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

Solution (Python):
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,m = li()
l = []

for i in range(n):l.append(li2())
l[0][0] = 1


for i in range(1,n):l[i][0] = 1*l[i-1][0] if l[i][0] != '

for j in range(1,m):l[0][j] = 1*l[0][j-1] if l[0][j] != '

for i in range(1,n):
    for j in range(1,m):
        if l[i][j] != '
            l[i][j] = l[i-1][j] + l[i][j-1]
        else:l[i][j] = 0
        l[i][j]%=mod

print(l[-1][-1])

Solution (Python):
R, C = tuple(map(int, input().split()))
grid = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C)] for _ in range(R)]
for row in range(R):
    if grid[row][0] != '
        dp[row][0] = 1
    else:
        break

for col in range(C):
    if grid[0][col] != '
        dp[0][col] = 1
    else:
        break





def gridpaths(R, C, grid, MAX=10 ** 9 + 7):
    for row in range(1, R):
        for col in range(1, C):
            if grid[row][col] != '
                dp[row][col] = (dp[row - 1][col] + dp[row][col - 1])%MAX
        
    return dp[-1][-1]


print(gridpaths(R, C, grid))

Solution (Python):
from collections import deque

h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
mod = 10**9 +7

dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
reach = [[False]*w for _ in range(h)]
que = deque(())

que.append((0,0))

while que:
    i,j = que.popleft()
    if i < h-1 and a[i+1][j] == '.':
        if dp[i+1][j] == 0:
            que.append((i+1,j))
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
    if j < w-1 and a[i][j+1] == '.':
        if dp[i][j+1] == 0:
            que.append((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())
G=[input() 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(G[i][j]=='
            continue
        if(i+1<H and G[i+1][j]!='
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD
        if(j+1<W and G[i][j+1]!='
            dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD
print(dp[H-1][W-1])

Solution (Python):
h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))
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 i+1<h and m[i+1][j]==".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if j+1<w and m[i][j+1]==".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Solution (Python):
h,w=map(int,input().split())
a=[input() for i in range(h)]
dp=[[0]*(w+1) for i in range(h+1)]
mod=10**9+7




dp[0][0]=1

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

Solution (Python):
H,W=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[0]*W for i in range(H)]

cnt=0
for i in range(H):
  if A[i][0]=='.' and cnt==0:
    D[i][0]=1
  else:
    cnt=1
cnt=0
for i in range(W):
  if A[0][i]=='.' and cnt==0:
    D[0][i]=1
  else:
    cnt=1
mod=10**9+7
for i in range(1,H):
  for j in range(1,W):
    if A[i][j]=='.':
      D[i][j]+=(D[i-1][j]+D[i][j-1])
      D[i][j]%=mod
print(D[-1][-1])

Solution (Python):
h,w=map(int,input().split())
mod=10**9+7
G=[['
for i in  range(1,h+1):
    G[i]=['
A=[[0]*(w+1) for i in range(h+1)]
A[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 G[i][j]=='.':
            A[i][j]=(A[i-1][j]+A[i][j-1])%mod
print(A[-1][-1])

Solution (Python):
x,y=map(int,input().split())
grd=[[0 for i in range(y)] for i in range(x)]
for i in range(x):
    s=input()
    for j in range(len(s)):
        if(s[j]=='.'):
            grd[i][j]=0
        else:
            grd[i][j]=-1

            
dp=[[0 for i in range(y)] for i in range(x)]
vi=[[0 for i in range(y)] for i in range(x)]
dp[0][0]=1
def grid(i,j):
    if(i==0 and j==0):
        return 1;
    if(i>=x or j>=y):
        return 0;
    if(grd[i][j]==-1):    
        return 0;
    if(vi[i][j]):
        return dp[i][j]
    vi[i][j]=1
    dp[i][j]=((dp[i-1][j])%(10**9+7)+dp[i][j-1]%(10**9+7))%(10**9+7)
    return dp[i][j];
for i in range(x):
    for j in range(y):
        dp[i][j]=grid(i,j)
print(dp[-1][-1])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
MOD = 10**9+7
dp = [[0]*1100 for _ in range(1100)]
H, W = input_nums()
a = []
for i in range(H):
    a.append(input())

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

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

field = []
for _ in range(H):
    tmp = list(input())
    tmp.append("
    field.append(tmp)
field.append(["
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for h in range(H):
    for w in range(W):
        if field[h][w] == "
            continue
        
        if field[h+1][w] == ".":
            dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= mod
        if field[h][w+1] == ".":
            dp[h][w+1] += dp[h][w]
            dp[h][w+1] %= mod

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

Solution (Python):
import math
import sys
sys.setrecursionlimit(1000000)
dp = [[0]*(1000+1) for x in range(1000+1)]
tab = []
def main():
    global n,m
    n,m = map(int,input().split())
    
    for x in range(n):
        tab.append(input())
    x = 0
    while x < n and tab[x][0] != "
        dp[x][0] = 1
        x += 1
    x = 0
    while x < m and tab[0][x] != "
        dp[0][x] = 1
        x += 1
    for x in range(1,n):
        for y in range(1,m):
            if tab[x][y]!="
                dp[x][y] = dp[x][y-1] + dp[x-1][y]
    
    print(dp[n-1][m-1]%(10**9+7))
main()

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

bignum = pow(10,9) + 7

mee = [[0 for i in range(w+1)] for j in range(h)]



for j in range(h):
    mee[j][0] = 0


for i in range(h):
    temp = input()
    for j in range(w):
        if temp[j] == "
            mee[i][j+1] = -1

for i in range(w+1):
    if mee[0][i] == -1:
        break
    mee[0][i] = 1



for i in range(1,h):
    for j in range(1,w+1):
        if mee[i][j] == -1:
            continue
        if mee[i - 1][j] > 0 and mee[i][j - 1] > 0:
            mee[i][j] = mee[i - 1][j] % bignum + mee[i][j - 1] %bignum

        elif mee[i - 1][j] > 0 or mee[i][j - 1] >0:
            mee[i][j] = max(mee[i-1][j],mee[i][j-1])

print(mee[-1][-1] % bignum)

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

dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
mod = int(1e9) + 7
for i in range(H):
    for j in range(W):
        if i > 0 and mark[i - 1][j] == '.':
            dp[i][j] += dp[i - 1][j] % mod
        if j > 0 and mark[i][j - 1] == '.':
            dp[i][j] += dp[i][j - 1] % mod
        dp[i][j] %= mod

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

Solution (Python):
inp = list(map(lambda x: int(x), input().split(" ")))
H = inp[0]
W = inp[1]

LIM = 10**9 + 7

field = [""]*H

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

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

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

for i in range(H):
    for j in range(W):
        n = 0
        if(field[H-1-i][W-1-j] != "
            if(H-i<H):
                n += dp[H-i][W-1-j]
            if(W-j<W):
                n += dp[H-1-i][W-j]
            if (n>0):
                if (n>=LIM):
                    n -= LIM
                dp[H-1-i][W-1-j] = n

print(dp[0][0])

Solution (Python):
H, W = map(int, input().split())
ans = [[0 for i in range(W)] for j in range(H)]
mark = []
for i in range(H):
    mark.append(input())

ans[0][0] = 1
mod = 10**9 + 7
for i in range(H):
    for j in range(W):
        if mark[i][j] == '
            continue
        if i > 0:
            ans[i][j] += ans[i-1][j]
        if j > 0:
            ans[i][j] += ans[i][j-1]
        ans[i][j] %= mod

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

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

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

for i in range(h):
    if f[i][0] != "
        dp[i][0] = 1
    else:
        break

for i in range(w):
    if f[0][i] != "
        dp[0][i] = 1
    else:
        break

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

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