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):
import sys
sys.setrecursionlimit(2<<28)

h, w = [int(i) for i in input().split()]
g = [list(input()) for _ in range(h)]
MOD = 10**9 + 7


def dfs(y, x):
    if not (0 <= y < h and 0 <= x < w):
        return 0
    elif g[y][x] == "
        return 0
    elif y == h - 1 and x == w - 1:
        return 1
    elif isinstance(g[y][x], int):
        return g[y][x]
    else:
        ret = 0
        for dy, dx in ((1, 0), (0, 1)):
            ret += dfs(y+dy, x+dx) % MOD
            ret %= MOD
        ret %= MOD
        g[y][x] = ret
        return ret


print(dfs(0, 0))

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):
import sys
def rr(): return sys.stdin.readline().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
def rrle(): return (line.rstrip() for line in sys.stdin.readlines())
def rrtl(): return [tuple(map(int, l.split())) for l in rrle()]
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math


def dpp(a, b=""): print("

def read():
    h, w = rrl()
    return (h, w, list(rrle()),)

def solve(h, w, field):
    dp = ms(h, w)
    dp[0][0] = 1
    for i in range(1, h):
        if field[i][0] == ".":
            dp[i][0] = dp[i-1][0]
    for i in range(1, w):
        if field[0][i] == ".":
            dp[0][i] = dp[0][i-1]

    for i in range(1, h):
        for j in range(1, w):
            if field[i][j] == ".":
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10**9 + 7)
    ans = dp[-1][-1]
    return ans

if __name__ == "__main__":
    
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

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

maze = []
for i in range(h):
    maze.append(input().rstrip())

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 maze[i][j] == '.':
            if i > 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j > 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod

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

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

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

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

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

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

Solution (Python):
r,c=list(int(i) for i in input().split())

za=10**9+7
A=[]
for i in range(r):
	B=input()
	k=list(B)
	A.append(k)
dp=[[0 for i in range(c+1)]for j in range(r+1)]
if A[r-1][c-1]=="
	dp[r-1][c-1]=0
else:
	dp[r-1][c-1]=1
for i in range(r-1,-1,-1):
	for j in range(c-1,-1,-1):
		if A[i][j]!="
			if(i<r-1 and j<c-1):
				if A[i+1][j]=="
					dp[i][j]=dp[i][j+1]
				elif A[i+1][j]!="
					dp[i][j]=dp[i+1][j]
				elif A[i+1][j]!="
					dp[i][j]=dp[i+1][j]+dp[i][j+1]
			elif j==c-1 and i!=r-1:
				if A[i+1][j]!="
					dp[i][j]=dp[i+1][j]
			elif(i==r-1 and j!=c-1):
				if A[i][j+1]!="
					dp[i][j]=dp[i][j+1]


print(dp[0][0]%za)

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 A[i][j] == '
            continue
        if i < 1 or A[i-1][j] == '
            pass
        else:
            dp[i][j] += dp[i-1][j]
        if j < 1 or A[i][j-1] == '
            pass
        else:
            dp[i][j] += dp[i][j-1]
        dp[i][j] %= MOD

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

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

Solution (Python):
H, W = map(int, input().split())
A = []
mod = 10**9
mod += 7

for h in range(H):
	A.append(list(input()))
dp = [[0 for w in range(W)] for h 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 A[i-1][j] != '
				dp[i][j] = (dp[i][j]%mod + dp[i-1][j]%mod)%mod
			if j > 0 and A[i][j-1] != '
				dp[i][j] = (dp[i][j]%mod + dp[i][j-1]%mod)%mod

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

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

Solution (Python):
def main():
    mod = 10**9+7
    H,W = list(map(int,input().split()))
    grid = [list(input()) for i in range(H)]
    DP = [[0]*W for i in range(H)]
    for i in range(H):
        if grid[i][0] == '.':
            DP[i][0] = 1
        else:
            break
    for i in range(W):
        if grid[0][i] == '.':
            DP[0][i] = 1
        else:
            break

    for i in range(1,H):
        for j in range(1,W):
            DP[i][j] = (DP[i-1][j]+DP[i][j-1])%mod if grid[i][j] == '.' else 0

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

if __name__ == "__main__":
    main()

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

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 a[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[H-1][W-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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

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

def rec(i,j):
  if dp[i][j] != -1:
    return dp[i][j]
  else:
    if A[i][j] == '
      return 0
    else:
      dp[i][j] = (rec(i+1, j) + rec(i, j+1)) % mod
      return dp[i][j]

print(rec(0,0))

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

for i in range(1, r):
  for j in range(1, c):
    if grid[i][j] != '
      dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mask
print(dp[-1][-1] % mask)

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

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

Solution (Python):
H, W = map(int, input().split())
A = []
mod = 10**9
mod += 7

for h in range(H):
	A.append(list(input()))
dp = [[0 for w in range(W)] for h 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 A[i-1][j] != '
				dp[i][j] = (dp[i][j]%mod + dp[i-1][j]%mod)%mod
			if j > 0 and A[i][j-1] != '
				dp[i][j] = (dp[i][j]%mod + dp[i][j-1]%mod)%mod

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

Solution (Python):
n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(input())
ans=[0]*(m+1)
ans[1]=1
for i in range(n):
  for j in range(m):
    if a[i][j]==".":
      ans[j+1]+=ans[j]
      ans[j+1]%=1000000007
    else :
      ans[j+1]=0
print(ans[m])

Solution (Python):
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
p = 10 ** 9 + 7

"""
dp[y][x]: y行x列に到達する方法の数
"""
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for y in range(h):
    for x in range(w):
        if y+1<h and maze[y+1][x] == ".":
            dp[y+1][x] = (dp[y+1][x] + dp[y][x]) % p
        if x+1<w and maze[y][x+1] == ".":
            dp[y][x+1] = (dp[y][x+1] + dp[y][x]) % p
print(dp[h-1][w-1])

Solution (Python):

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    mod = 1000000007

    H, W = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if a[i][j]=='
                a[i][j] = 0
    a[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j]=='.':
                if i==0:
                    a[i][j] = a[i][j-1]
                elif j==0:
                    a[i][j] = a[i-1][j]
                else:
                    a[i][j] = a[i-1][j] + a[i][j-1]
    print(a[H-1][W-1]%mod)



if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    mod = 1000000007

    H, W = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if a[i][j]=='
                a[i][j] = 0
    a[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j]=='.':
                if i==0:
                    a[i][j] = a[i][j-1]
                elif j==0:
                    a[i][j] = a[i-1][j]
                else:
                    a[i][j] = a[i-1][j] + a[i][j-1]
    print(a[H-1][W-1]%mod)



if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Rt = [[INF]*W for _ in range(H)]
  Rt[start[0]][start[1]]=1
  q = deque([])
  q.append(start)
  while len(q)!=0:
    h,w = 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 Gd[hs][ws]=='.':
        if Rt[hs][ws]==INF:
          q.append([hs,ws])
        Rt[hs][ws] = (Rt[hs][ws] + Rt[h][w])%mod
  return Rt[H-1][W-1]
print(dfs([0,0]))

Solution (Python):
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Rt = [[INF]*W for _ in range(H)]
  Rt[start[0]][start[1]]=1
  q = deque([])
  q.append(start)
  while len(q)!=0:
    h,w = 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 Gd[hs][ws]=='.':
        if Rt[hs][ws]==INF:
          q.append([hs,ws])
        Rt[hs][ws] = (Rt[hs][ws] + Rt[h][w])%mod
  return Rt[H-1][W-1]
print(dfs([0,0]))

Solution (Python):
from collections import deque
mod=10**9+7
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = 0
direc = [[1,0],[0,1]]
def dfs(start):
  Dis = [[INF]*W for _ in range(H)]
  Dis[start[0]][start[1]]=1
  q = deque([])
  q.append(start)
  while len(q)!=0:
    h,w = 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 Gd[hs][ws]=='.':
        if Dis[hs][ws]==INF:
          q.append([hs,ws])
        Dis[hs][ws] = (Dis[hs][ws] + Dis[h][w])%mod
  return Dis[H-1][W-1]
print(dfs([0,0]))

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

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

grid = []

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

mod = 10**9+7
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]=='
      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[n-1][m-1]%mod)

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

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


dp = [[0 for _ in range(m)] for i in range(n)]

dp[0][0]=1
mod = 10**9 + 7
for i in range(n):
  for j in range(m):
    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[n-1][m-1]%mod)

Solution (Python):
H,W=map(int,input().split())
a=[]
mod=10**9+7

for i in range(H):
    temp=list(map(str,input()))
    a.append(temp)

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:continue
        if a[h][w]=="
        if h-1<0:
            dp[h][w]=dp[h][w-1]%mod
        elif w-1<0:
            dp[h][w] = dp[h-1][w]%mod
        else:
            dp[h][w] = (dp[h][w -1] + dp[h -1][w])%mod

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

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

mod=10**9+7

dp=[[0]*W for i in range(H)]
dp[0][0]=1
for h in range(H):
    for w in range(W):
        if a[h][w]=='
        if h>=1:dp[h][w]+=dp[h-1][w]
        if w>=1:dp[h][w]+=dp[h][w-1]

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

def dfs(x, y):
  if x == W-1 and y == H-1:
    return 1
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx >= W or ny >= H:
      continue
    if dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif field[ny][nx] == ".":
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx >= W or ny >= H:
      continue

    if nx == W-1 and ny == H-1:
      ret += 1
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
    elif field[ny][nx] == ".":
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

def dfs(x, y):
  ret = 0
  for nx, ny in ((1,0), (0,1)):
    nx += x
    ny += y
    if nx == W-1 and ny == H-1:
      ret += 1
      continue
    elif nx >= W or ny >= H:
      continue
    elif dp[ny][nx] > -1:
      ret += dp[ny][nx]
      continue
    elif field[ny][nx] == "
      continue
    else:
      ret += dfs(nx, ny)
  dp[y][x] = ret % MOD
  return ret

dfs(0,0)
print(dp[0][0])

Solution (Python):
from sys import stdin
def main():
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[0]*H
    for i in range(H):
        s=readline().strip()
        grid[i]=s
    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:
                if grid[i+1][j]==".":
                    dp[i+1][j]+=dp[i][j]
                    dp[i+1][j]%=mod
            if j+1<W:
                if grid[i][j+1]==".":
                    dp[i][j+1]+=dp[i][j]
                    dp[i][j+1]%=mod
    print(dp[H-1][W-1])

if __name__=="__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
c=["
mod=10**9+7

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

direction=[(0,-1),(0,1),(1,0),(-1,0)]
for h in range(1,H+1):
    for w in range(1,W+1):
        for x,y in direction:
            if c[h+x][w+y]==".":
                dp[h+x][w+y]=(dp[h+x][w+y]+dp[h][w])%mod

print(dp[H][W])

Solution (Python):
p = 10**9+7
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

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 maze[i-1][j-1] == '.':
            dp[i][j] += dp[i-1][j]%p + dp[i][j-1]%p


ans = dp[h][w]%p

print(ans)

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

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

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

dp[1][0] = 1

for w in range(1,W+1):
    for h in range(1,H+1):
        if a_matrix[h-1][w-1] == ".":
            dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % mod
        else:
            dp[h][w] = 0
print(dp[H][W])

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

MOD = 10**9 + 7

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


for i in range(w):
    if filed[0][i] == '
        break
    dp[0][i] = 1
for i in range(h):
    if filed[i][0] == '
        break
    dp[i][0] = 1
    


for i in range(1, h):
    for j in range(1, w):
        if filed[i][j] == '
            continue
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD

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

Solution (Python):
h,w=map(int,input().split())
l=[[0]*w]*h
m=[""]*h
for k in range(h):
  m[k]=input()
l[0][0]=1
for k in range(h):
  for j in range(w):
    if m[k][j]=="
      l[k][j]=0
    else:
      if k==0:
        if j!=0:
          l[k][j]=l[0][j-1]
      elif j==0:
        if k!=0:
          l[k][j]=l[k-1][j]
      else:
        l[k][j]=l[k-1][j]+l[k][j-1]
print(l[h-1][w-1]%1000000007)

Solution (Python):

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

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

mod = 10**9+7

a = []

for i in range(H):
    A = list(input())
    a.append(A)

lis[0][0] = 1
for i in range(H):

    for j in range(W):

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

        if i > 0:
            lis[i][j] += lis[i-1][j]
        if j > 0:
            lis[i][j] += lis[i][j-1]

        lis[i][j] %= mod

print (lis[-1][-1])

Solution (Python):
H,W=map(int, input().split())
C=[[0]*W for i in range(H)]
D=[[] for i in range(H)]
p=10**9+7
for i in range(H):
    inp = input()
    for j in range(W):
        D[i].append(inp[j])

C[0][0]=1
for i in range(1,W):
    if(D[0][i]=="."):
        C[0][i]=C[0][i-1]
    else:
        C[0][i]=0

for i in range(1,H):
    if(D[i][0]=="."):
        C[i][0]=C[i-1][0]
    else:
        C[i][0]=0

for i in range(1,H):
    for j in range(1,W):
        if(D[i][j]=="
            C[i][j]=0
        else:

            C[i][j]=C[i-1][j]+C[i][j-1]
            C[i][j]=C[i][j]%p
print(C[H-1][W-1])

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

def main():
    """dpをするときのてんぷれコ―ド"""
    
    mod = 10**9+7
    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] == ".":             
                if i == 0 and j == 0:
                    continue
                elif i == 0 and a[i][j-1] == ".":
                    dp[i][j] += dp[i][j-1]
                elif j == 0 and a[i-1][j] == ".":
                    dp[i][j] += dp[i-1][j]
                else:
                    if a[i][j-1] == ".":
                        dp[i][j] += dp[i][j-1]
                    if a[i-1][j] == ".":
                        dp[i][j] += dp[i-1][j]

    

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

if __name__ == '__main__':
    main()

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

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

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

dp[1][1] = 1

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

print (dp[H][W])

Solution (Python):

def main():
    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 maze[i][j] == '
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]

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


main()

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

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

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
M = 10**9 + 7
for i in range(H):
  for j in range(W):
    if MAP[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] %= M
print(dp[-1][-1])

Solution (Python):

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

mod = 1000000007


dp = [[0] * W for i 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][j] == '
      continue
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

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

Solution (Python):
import sys
import math
from collections import deque
import copy

MOD = 10 ** 9 + 7
H, W = map(int, input().split())

a = [["
for i in range(H):
    p = deque(list(input()))
    p.appendleft("
    p.append("
    a.append(list(p))
a.append(["

dp = [[0 for _ in range(W + 10)] for _ in range(H + 10)]
dp[0][1] = 1
for i in range(1, H + 1):
    for l in range(1, W + 1):
        if a[i][l] != "
            dp[i][l] = (dp[i][l - 1] + dp[i - 1][l]) % MOD
print(dp[H][W] % MOD)

Solution (Python):

import sys

MOD = 1000000007  

def init(H, W, a):
    val=1
    for i in range(W):
        if a[0][i]=="
            val=0
            continue
        a[0][i]=val

    val=1
    for i in range(H):
        if a[i][0]=="
            val=0
            continue
        a[i][0]=val

def solve(H: int, W: int, a: "List[List[str]]"):
    init(H, W, a)
    for i in range(1,H):
        for j in range(1,W):
            if a[i][j]=="
            val=0
            if a[i-1][j]!="
            if a[i][j-1]!="
            a[i][j]=val%MOD
    print(a[H-1][W-1])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    
    a = [list(next(tokens)) for _ in range(H)]  
    solve(H, W, a)

if __name__ == '__main__':
    main()

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

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

for i in range(h):
    for j in range(w):
        if j+1 < w and rule[i][j+1] == '.':
            graph[i][j+1] = (graph[i][j+1] + graph[i][j]) % mod
        if i+1 < h and rule[i+1][j] == '.':
            graph[i+1][j] = (graph[i+1][j] + graph[i][j]) % mod


print(graph[-1][-1])

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

def main():
    h,w=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    for j in range(w):
        for i in range(h):
            if s[i][j]=='
                continue
            else:
                if j==0:
                    if i==0:
                        dp[i][j]=1
                    else:
                        dp[i][j]=dp[i-1][j]%(10**9+7)
                elif i==0:
                    dp[i][j]=dp[i][j-1]%(10**9+7)
                else:
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%(10**9+7)
    print(dp[h-1][w-1])

if __name__ == '__main__':
    main()

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


dp = [[0 for _ in range(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]
            dp[i+1][j] %= 1000000007
        if j + 1 < w and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= 1000000007

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

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