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}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{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.



Sample input:
3 4
...#
.#..
....


Sample output:
3

Submission status: Accepted

Solution code:
def solve():
    MOD = 10 ** 9 + 7
    H, W = map(int, input().split())
    maze = ['' for _ in range(H)]
    for i in range(H):
        maze[i] = input()

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

    for i in range(1, H):
        for j in range(1, W):
            if maze[i][j] != '#':
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                dp[i][j] %= MOD
    print(dp[H-1][W-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W = map(int, input().split())
dp = [[] for _ in range(H)]
for i in range(H):
	data = input()
	for j in range(W):
		if data[j] == "." : dp[i].append(1)
		else : dp[i].append(0)
for i in range(H):
	for j in range(W):
		if(dp[i][j]!=0):
			if(i > 0 and j > 0) : dp[i][j] = dp[i-1][j]+dp[i][j-1]
			elif(i > 0) : dp[i][j] = dp[i-1][j]
			elif(j > 0) : dp[i][j] = dp[i][j-1]
print(dp[H-1][W-1]%(10**9+7))

Submission status: Accepted

Solution code:

modula = 10**9 + 7

def solve(H, W, grid):
  dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
  dp[1][1] = 1

  for h in range(1, H + 1):
    for w in range(1, W + 1):
      if grid[h - 1][w - 1] == 0:
        continue

      if h > 1:
        if grid[h - 2][w - 1] == 1:
          dp[h][w] += dp[h - 1][w] % modula
      if w > 1:
        if grid[h - 1][w - 2] == 1:
          dp[h][w] += dp[h][w - 1] % modula

  print(dp[H][W] % modula)

  
def iln(): return list(map(int, input().split()))

  
H, W = iln()
grid = []
for h in range(H):
  grid.append(list(map(lambda i: 1 if i == '.' else 0, input())))
  
solve(H, W, grid)

Submission status: Accepted

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

mod = 10**9+7
maze = [[0 for _ in range(W)] for _ in range(H)]

mm = 1
for w in range(W):
    if a[0][w] == '#':
        mm = 0
    maze[0][w] = mm

mm = 1
for h in range(H):
    if a[h][0] == '#':
        mm = 0
    maze[h][0] = mm

for h in range(1,H):
    for w in range(1,W):
        if a[h][w] == ".":
            maze[h][w] = (maze[h-1][w]+maze[h][w-1])%mod

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

Submission status: Accepted

Solution code:
import queue

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

#[y][x]
a = [list(input()) for i in range(H)]
mod = 10**9 + 7

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

#y
for i in range(H):
    #x
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0 and j == 1:
            if a[i][j] != "#":
                dp[i][j] = 1
            continue
        if i == 1 and j == 0:
            if a[i][j] != "#":
                dp[i][j] = 1
            continue

        if a[i][j] == "#":
            dp[i][j] = 0
        else:
            if 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]

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

Submission status: Accepted

Solution code:
import queue

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

#[y][x]
a = [list(input()) for i in range(H)]
mod = 10**9 + 7

#[y][x]
dp = [[1 for _ in range(W)] for _ in range(H)]

#1行目
for i in range(1,W):
    if a[0][i] == "#":
        dp[0][i] = 0
        for j in range(i+1,W):
            dp[0][j] = 0
        break


#1列目
for i in range(1,H):
    if a[i][0] == "#":
        dp[i][0] = 0
        for j in range(i+1,H):
            dp[j][0] = 0
        break

#y
for i in range(1,H):
    #x
    for j in range(1,W):
        if a[i][j] == "#":
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

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

Submission status: Accepted

Solution code:
#Educational DP Contest
#H-Grid1


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


#dp table
#座標をそのままdpテーブルとして見立てることができる。
#要素はその場所まで行ける手順の数
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1

#process1
#移動は→↓の２通りのみなので、その方向に探索していけば良い。
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            continue
        if i > 0: #i-1を参照するため端っこは除く
            dp[i][j] += dp[i-1][j]
        if j > 0:
            dp[i][j] += dp[i][j-1]
        dp[i][j] %= mod


#output process
print(dp[-1][-1])

Submission status: Accepted

Solution code:
mod = 10**9+7
H, W = [int(i) for i in input().split()]
a = [input() for _ in range(H)]
dp = [[0]*W for _ in range(2)]
dp[0][0] = 1

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

Submission status: Accepted

Solution code:
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 > 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])

Submission status: Accepted

Solution code:
import math
import sys
import collections
import sys

sys.setrecursionlimit(200000)

input = sys.stdin.readline
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
# for i in range(H):
#     for j in range(W):
#         if C[i][j] == ".":
#             C[i][j] = 0
#         else:
#             C[i][j] = 1
d = [[1, 0], [0, 1]]
dp = [[0] * (W  ) for i in range(H ) ]
sx = 1
sy = 1
MOD = 10 ** 9 + 7
dp[0][0] = 1
for w in range(W):
    for h in range(H):
        if h  <  H - 1  and C[h + 1][w] == ".":
            dp[h + 1][w] += dp[h][w]
            dp[h + 1][w] %= MOD
        if w  <  W - 1  and C[h][w + 1] == ".":
            dp[h][w + 1] += dp[h][w]
            dp[h][w + 1] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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


dp = [[0]*(W+1) for h in range(H+1)]
dp[0][1] = 1 
for h in range(1, H+1):
  for w in range(1, W+1):
    if grid[h-1][w-1] == '#':
      continue
    
    dp[h][w] = (dp[h][w-1] + dp[h-1][w]) % MOD

print(dp[H][W])

Submission status: Accepted

Solution code:
def grid1(lines):
    mod = 10 ** 9 + 7
    
    w = len(lines[0])
    cur = [0] * w
    nxt = [0] * w
    cur[0] = 1

    for line in lines:
        nxt[-1] = 0
        for i in range(w):
            if line[i] == "#":
                nxt[i] = 0
            else:
                nxt[i] = (cur[i] + nxt[i - 1]) % mod
        cur, nxt = nxt, cur

    return cur[-1]


def main():
    h, w = [int(x) for x in input().split()]
    lines = [None] * h
    for i in range(h):
        lines[i] = input()

    return grid1(lines)


print(main())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
# 0-indexed

dp = [[0 for _ in range(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] != "#":
      dp[h][w] = dp[h-1][w] + dp[h][w-1]
      dp[h][w] %= 10**9 + 7

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
g = [input() for i in range(h)]
dp = [[0]*w for i in range(h)]
for i in range(h):
    if g[i][0] == '#':
        break
    dp[i][0] = 1
for i in range(w):
    if g[0][i] == '#':
        break
    dp[0][i] = 1

for y in range(h-1):
    for x in range(w-1):
        if g[y+1][x+1] == '#':
            continue
        dp[y+1][x+1] = dp[y+1][x] + dp[y][x+1]
        dp[y+1][x+1] %= mod
print(dp[-1][-1])
# pprint.pprint(dp)

Submission status: Accepted

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

H, W = map(int, input().split())
a = ["#"+input().strip()+"#" for _ in range(H)]
a = ["#"*(W+2)] + a + ["#"*(W+2)]
a[1] = "."+a[1][1:]

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

for y in range(1, H+1):
    for x in range(1, W+1):
        if a[y][x] == '.':
            t = 0
            if a[y][x-1] == '.':
                t += dp[y][x-1]
            if a[y-1][x] == '.':
                t += dp[y-1][x]
            dp[y][x] = t % mod
print(dp[H][W])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
g = [[x for x in input()] for _ in range(h)]

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

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            continue
        if i != 0:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= 10**9+7
        if j != 0:
            dp[i][j] += dp[i][j-1]
            dp[i][j] %= 10**9+7

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = 10**9 + 7
dp = [0]*((N+1)*(M+1))
dp[1] = 1
for i in range(1, N+1):
    s = input().strip()
    for j in range(1, M+1):
        if s[j-1] == ".":
            dp[i*(M+1)+j] = (dp[(i-1)*(M+1) + j] + dp[i*(M+1) + j-1])%mod
print(dp[N*(M+1)+M])

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def grid_1(): 
    H, W = wczytaj_liste()
    siatka = []
    for i in range (H): 
        siatka.append(input())
    czy_mozna = True
    ile_mozliwosci = [[0 for i in range(W)] for j in range(H)]
    
    for i in range(W): 
        if siatka[0][i] == '.' and czy_mozna:
            ile_mozliwosci[0][i]= 1
        else: 
            czy_mozna = False
    czy_mozna = True
    for j in range(H):
        if siatka[j][0]=='.' and czy_mozna: 
            ile_mozliwosci[j][0]=1
        else: 
            czy_mozna = False
    for i in range(1,W):
        for j in range (1,H):
            if siatka[j][i] == '.':
                ile_mozliwosci[j][i] = (ile_mozliwosci[j-1][i]+ile_mozliwosci[j][i-1]) %(10**9+7)
            else:
                ile_mozliwosci[j][i] = 0
    print(ile_mozliwosci[H-1][W-1])
    
grid_1()

Submission status: Accepted

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

As = []
for _ in range(H):
  As.append(input())
paths = [[0 for _ in range(W)] for _ in range(H)]

paths[0][0] = 1

mod = 1e+9 + 7

for width in range(W):
  for height in range(H):
    if As[height][width] == "#":
      # 壁のマスであればスキップする
      continue
    if height < H-1:
      if As[height + 1][width] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height + 1][width] = int((paths[height + 1][width] + paths[height][width]) % mod)
    if width < W-1:
      if As[height][width + 1] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height][width + 1] = int((paths[height][width + 1] + paths[height][width]) % mod)

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

Submission status: Accepted

Solution code:
div = (10**9)+7
h,w = map(int, input().split())

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

for i in range(h):
    a_h = input()
    for j in range(w):
        if((i==0) & (j==0)):
            dp[i+1][j+1] = 1
        else:
            if(a_h[j] == '.'):
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1])%div

print(dp[h][w])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [input() for _ in range(h)]
ans = [[0] * w for _ in range(h)]

ans[0][0] = 1
for i, row in enumerate(grid):
    for j, cell in enumerate(row):
        if cell == '#' or (i == 0 and j == 0):
            continue
        elif i == 0:
            ans[i][j] = ans[i][j-1]
        elif j == 0:
            ans[i][j] = ans[i-1][j]
        else:
            ans[i][j] = ans[i][j-1] + ans[i-1][j]
if ans[-1][-1] >= 10**9 + 7:
    ans[-1][-1] %= 10**9 + 7

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

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    board = [[int(s == ".") for s in 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 board[i][j]:
                dp[i][j] %= mod
            else:
                dp[i][j] = 0
            dp[i+1][j] += dp[i][j]
            dp[i][j+1] += dp[i][j]
    print(dp[H-1][W-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(H: int, W: int, a: "List[List[str]]"):
    grid = [[0]*W for _ in range(H)]

    grid[0][0] = 1
    for i in range(H):
        for j in range(W):
            if a[i][j] == "#":
                continue
            if i > 0:
                grid[i][j] += grid[i-1][j]
                grid[i][j] %= MOD
            if j > 0:
                grid[i][j] += grid[i][j-1]
                grid[i][j] %= MOD
    print(grid[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))  # type: int
    W = int(next(tokens))  # type: int
    a = [next(tokens) for _ in range(H)]
    solve(H, W, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a, b = list(map(int, input().split()))
grid = list()
grid.append([-1 for _ in range(b + 2)])
for t in range(0, a):
    grid.append([-1])
    line = list(input())
    for k in range(len(line)):
        if line[k] == '#':
            grid[t + 1] += [-1]
        else:
            grid[t + 1] += [0]
    grid[t + 1] += [-1]
grid.append([-1 for _ in range(b + 2)])
grid[1][1] = 1
for x in range(1, a + 1):
    for y in range(1, b + 1):
        if grid[x][y] > 0:
            if grid[x + 1][y] != -1:
                grid[x + 1][y] += grid[x][y]
            if grid[x][y + 1] != -1:
                grid[x][y + 1] += grid[x][y]
print(grid[-2][-2] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [input() for i 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 a[i][j] == ".":
            if i+1 < h:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD
            if j+1 < w:
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= MOD

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

Submission status: Accepted

Solution code:
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(h):
  for x in range(w):
    if y < h-1 and A[y+1][x] == ".":
      dp[y+1][x] += dp[y][x]
      dp[y+1][x] %= MOD
    if x < w-1 and A[y][x+1] == ".":
      dp[y][x+1] += dp[y][x]
      dp[y][x+1] %= MOD
print(dp[h-1][w-1])

Submission status: Accepted

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

MOD = 10**9 + 7

# dp[i][j]: (i,j)までの経路の総数
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] % MOD
        if j+1 < W and a[i][j+1] == ".":
            dp[i][j+1] += dp[i][j] % MOD

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [list(map(str,input())) for _ in range(h)]
#dp[i][j]は上からi番目,左からj番目 dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]
mod = 10**9+7
dp = [[0]*w for i in range(h)]
for k in range(h):
  if a[k][0] == ".":
    dp[k][0] = 1
  else:
    break
for l in range(w):
  if a[0][l] == ".":
    dp[0][l] = 1
  else:
    break
for i in range(h-1):
  for j in range(w-1):
    dp[i+1][j+1] = (dp[i][j+1]+dp[i+1][j]) % mod
    if a[i+1][j+1] == "#":
      dp[i+1][j+1] = 0
print(dp[-1][-1]%mod)
#print(dp)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = []
for i in range(H):
    a_i = [i for i in input()]
    a.append(a_i)
dp = [[0 for i in range(W)] for j in range(H)]
# init
for h in range(H):
    if a[h][0] == "#":
        break
    dp[h][0] = 1
for w in range(W):
    if a[0][w] == "#":
        break
    dp[0][w] = 1

for h in range(1, H):
    for w in range(1, W):
        dp[h][w] = dp[h][w - 1] + dp[h - 1][w] if a[h][w] == "." else 0
print(dp[-1][-1] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
def main():
    a = [int(x) for x in input().split()]
    H, W = a[0], a[1]
    grid = [input() for _ in range(H)]
    dp = [[0 for _ in range(W)] for _ in range(H)]
    modder = int(1e9 + 7)
    dp[0][0] = 1
    for row in range(H):
        for col in range(W):
            for row2 in range(row, row+2):
                col2 = col + 1 if row2 == row else col
                if row2 < H and col2 < W and grid[row2][col2] == ".":
                    dp[row2][col2] = (dp[row][col] + dp[row2][col2]) % modder
    print(dp[H-1][W-1])


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
  for j in range(W):
    if i + 1 < H:
      if S[i + 1][j] == ".":
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
    if j + 1 < W:
      if S[i][j + 1] == ".":
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from sys import stdin
n, m = map(int, stdin.readline().split())
grid = []
for i in range(n):
    row = list(input())
    grid.append(row)

dp = [[0 for j in range(m)] for i in range(n)]
for i in range(m):
    if grid[0][i] == '.':
        dp[0][i] = 1
    else:
        break
for i in range(n):
    if grid[i][0] == '.':
        dp[i][0] = 1
    else:
        break

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

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout

n,m = map(int,stdin.readline().split())
grid = []
for i in range(n):
    row = input()
    grid.append(row)
dp = [ [0 for j in range(m)] for i in range(n) ]
for i in range(m):
    if grid[0][i]=='#':
        break
    dp[0][i] = 1
for i in range(n):
    if grid[i][0]=='#':
        break
    dp[i][0] = 1
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]
        dp[i][j] %= 10**9+7
print(dp[n-1][m-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7

for i in range(h):
  for j in range(w):
    if grid[i][j]=="#":
      dp[i][j]=0
    elif i==0 and j==0:
      dp[i][j]=1
    else:
      up=0
      left=0
      if i>0:
        up=dp[i-1][j]
      if j>0:
        left=dp[i][j-1]
      dp[i][j]=(up+left)%DIV
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
p = 10**9+7
H,W = map(int,input().split())
A = ["#"*(W+1)]
for _ in range(H):
    a = input().strip()
    a = "#"+a
    A.append(a)
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[H][W] = 1
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if A[i][j]=="#":continue
        if j+1<=W:
            dp[i][j] = (dp[i][j]+dp[i][j+1])%p
        if i+1<=H:
            dp[i][j] = (dp[i][j]+dp[i+1][j])%p
print(dp[1][1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#h-%E5%95%8F%E9%A1%8C---grid-1
    # ◯：自力で気がつけた点
    # △：自力で気がつけなかった点/解説を読めば理解できた点
    # ×：解説を読んでも理解できていない点

    # ◯経路のパターン数を管理
    # △2次元の配列で管理
    # ◯初期値は1通り
    dp[0][0] = 1

    for i in range(h):
        for j in range(w):
            # 配るDP
            # △数え上げDPでは，dp[to] += dp[from]が基本形
            # 次に進むマスがグリッドの範囲内，かつ，進むことができる
            if (j + 1 < w) and (a[i][j + 1] == '.'):
                dp[i][j + 1] += dp[i][j]
                dp[i][j + 1] %= mod

            if (i + 1 < h) and (a[i + 1][j] == '.'):
                dp[i + 1][j] += dp[i][j]
                dp[i + 1][j] %= mod

    # △求めるべき経路数
    print(dp[h - 1][w - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    H,W=list(map(int,sys.stdin.readline().split()))
    MAP=[]
    for i in range(H):
        MAP.append([0 if x=="#" else 1 for x in sys.stdin.readline()][:-1])
    #1:道　0:ブロック

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

    for x in range(1,W):
        if MAP[0][x]:
            dp[0][x]=dp[0][x-1]
        else:
            dp[0][x]=-1


    for y in range(1,H):
        if MAP[y][0]:
            dp[y][0]=dp[y-1][0]
        else:
            dp[y][0]=-1

    for y in range(1,H):
        for x in range(1,W):
            if MAP[y][x]==0:
                dp[y][x]=-1
            else:
                o=0
                if dp[y][x-1]+1:
                    o+=dp[y][x-1]
                if dp[y-1][x]+1:
                    o+=dp[y-1][x]
                if not (dp[y-1][x]+1 or dp[y][x-1]+1):
                    o=-1
                else:
                    o%=10**9+7

                dp[y][x]=o

    if dp[H-1][W-1]==-1:
        dp[H-1][W-1]+=1
    print(dp[H-1][W-1])

main()

Submission status: Accepted

Solution code:
def main():
    MOD = int(1e9 + 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 j in range(w):
            if grid[i][j] != '#':
                if i > 0:
                    dp[i][j] += dp[i-1][j]

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

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

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    MOD = int(1e9 + 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 j in range(w):
            if grid[i][j] != '#':
                if i > 0:
                    dp[i][j] += dp[i-1][j]

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

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    MOD = int(1e9 + 7)
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]

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

    for i in range(h):
        for j in range(w):
            if grid[i][j] != '#':
                if i == 0 and j == 0:
                    dp[i][j] = 1
                
                if i > 0:
                    dp[i][j] += dp[i-1][j]

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

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

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



if __name__ == "__main__":
    main()