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:
h,w=map(int,input().split())
mod=10**9+7
T=[]
for i in range(h):
  T.append(input())
DP=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if i==0:
      if j==0:
        DP[i][j]=1
      elif T[i][j]=="#":
        DP[i][j]=0
      else:
        DP[i][j]=DP[i][j-1]
    else:
      if j==0:
        if T[i][j]=="#":
          DP[i][j]=0
        else:
          DP[i][j]=DP[i-1][j]
      else:
        if T[i][j]=="#":
          DP[i][j]=0
        else:
          DP[i][j]=(DP[i-1][j]+DP[i][j-1])%mod
print(DP[h-1][w-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mod=10**9+7
T=[]
for i in range(h):
  T.append(input())
DP=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if i==0:
      if j==0:
        DP[i][j]=1
      elif T[i][j]=="#":
        DP[i][j]=0
      else:
        DP[i][j]=DP[i][j-1]
    else:
      if j==0:
        if T[i][j]=="#":
          DP[i][j]=0
        else:
          DP[i][j]=DP[i-1][j]
      else:
        if T[i][j]=="#":
          DP[i][j]=0
        else:
          DP[i][j]=(DP[i-1][j]+DP[i][j-1])%mod
print(DP[h-1][w-1])

Submission status: Accepted

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

WARU = 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 a[i][j] == "#":
            continue
        
        dp[i][j] %= WARU

        dp[i+1][j] += dp[i][j]
        dp[i][j+1] += dp[i][j]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

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

    for i in range(1, W):
        dp[0][i] = dp[0][i-1] if a[0][i] == '.' else 0

    for i in range(1, H):
        dp[i][0] = dp[i-1][0] if a[i][0] == '.' else 0
    
    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
    return dp[-1][-1]


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) ]  # type: "List[str]"
    result = solve(H, W, a)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
mod=10**9+7
h+=2
w+=2
a.append("#"*w)
for i in range(h-2):
    a.append("#"+input()+"#")
a.append("#"*w)

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

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

Submission status: Accepted

Solution code:
import fileinput

def find_path_count(n, m, wall_set):
    modulo = 10**9 + 7
    path_table = []
    def get_path_count(x, y):
        if x < 0 or y < 0 or (x, y) in wall_set:
            return 0
        return path_table[x][y]

    for x in range(n):
        path_table.append([0] * m)
        for y in range(m):
            if x == 0 and y == 0:
                path_table[x][y] = 1
            else:
                path_table[x][y] = (get_path_count(x - 1, y) + get_path_count(x, y - 1)) % modulo

    return path_table[n - 1][m - 1]

def parse_vall_set(map_strings):
    wall_set = set()
    for x, s in enumerate(map_strings):
        for y, ch in enumerate(s):
            if ch == "#":
                wall_set.add((x, y))
    return wall_set


inp = fileinput.FileInput()
n, m = inp.readline().split(" ")
n, m = int(n), int(m)
map_strings = []
for _ in range(n):
    map_strings.append(inp.readline())

print(find_path_count(n, m, parse_vall_set(map_strings)))

Submission status: Accepted

Solution code:
mo=10**9+7
h,w=map(int,input().split())
m=[[0]*(w+2) for i in range(h+2)]
for i in range(h):
    for (j,s) in enumerate(input()):
        m[i+1][j+1]=0 if s=='#' else 1

for i in range(1,h+1):
    for j in range(1,w+1):
        if i*j==1:
            0
        elif m[i][j]!=0:
            m[i][j]=m[i-1][j]+m[i][j-1]
            m[i][j]%=mo
        
print(m[h][w]%mo)

Submission status: Accepted

Solution code:
# atcoder DP 動的計画法
# H Grid 1

WALL = -1
ROAD = 0

# 問題文の入力を受け取る
def get_inputs():
    # 迷路の横幅Wと高さHを受け取る
    H, W = map(int, input().split())

    # 迷路の地図情報を受け取る
    # .：通路 int 0に変換
    # #：壁 int -1に変換
    maze = []
    for _ in range(H):
        maze.append([ROAD if c == "." else WALL for c in input()])
    
    return H, W, maze

H, W, maze = get_inputs()

# mazeを動的計画法のテーブルとして扱う
# 左上隅から探索し、行く先(右もしくは下）が迷路の範囲内であり、かつ通路であれば、経路数を加算する
# 配るdpの考え方でテーブル作成

maze[0][0] = 1
for j in range(H):
    for i in range(W):
        if maze[j][i] != WALL:
            if 0 <= i + 1 < W and 0 <= j < H and maze[j][i + 1] != WALL:
                maze[j][i + 1] += maze[j][i]
            if 0 <= i < W and 0 <= j + 1 < H and maze[j + 1][i] != WALL:
                maze[j + 1][i] += maze[j][i]

print(maze[H - 1][W - 1] % (10 ** 9 + 7))

Submission status: Accepted

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

MOD = 10**9+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 i != 0:
            dp[i][j] += dp[i-1][j]
        if j != 0:
            dp[i][j] += dp[i][j-1]
        if a[i][j] == "#":
            dp[i][j] = 0
print(dp[H-1][W-1] % MOD)

Submission status: Accepted

Solution code:
def main():
	H, W = map(int, input().split())
	STAGE = [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 + 1 < H and STAGE[y + 1][x] == ".":
				dp[y + 1][x] += dp[y][x] % MOD
			if x + 1 < W and STAGE[y][x + 1] == ".":
				dp[y][x + 1] += dp[y][x] % MOD

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

main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
STAGE = [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 + 1 < H and STAGE[y + 1][x] == ".":
			dp[y + 1][x] += dp[y][x] % MOD
		if x + 1 < W and STAGE[y][x + 1] == ".":
			dp[y][x + 1] += dp[y][x] % MOD

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
STAGE = [list(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 + 1 < H and STAGE[y + 1][x] == ".":
			dp[y + 1][x] += dp[y][x] % MOD
		if x + 1 < W and STAGE[y][x + 1] == ".":
			dp[y][x + 1] += dp[y][x] % MOD

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

Submission status: Accepted

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

dp = [[0 for _ in range(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 + 1 < H and STAGE[y + 1][x] == ".":
			dp[y + 1][x] += dp[y][x] % MOD
		if x + 1 < W and STAGE[y][x + 1] == ".":
			dp[y][x + 1] += dp[y][x] % MOD

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

Submission status: Accepted

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

dp = [[0 for _ in range(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 + 1 < H and STAGE[y + 1][x] == ".":
			dp[y + 1][x] += dp[y][x]
			if MOD < dp[y + 1][x]:
				dp[y + 1][x] -= MOD
		if x + 1 < W and STAGE[y][x + 1] == ".":
			dp[y][x + 1] += dp[y][x]
			if MOD < dp[y][x + 1]:
				dp[y][x + 1] -= MOD

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

grid = [list(input()) for _ in range(H)]

# dp[h][w] = (0,0) から (h,w) までの経路の本数
dp = [[0] * W for _ in range(H)]
# 初期値
dp[0][0] = 1

# mod用
MOD_INT = 10 ** 9 + 7

for h in range(H):
    for w in range(W):
        # 右が範囲内の空マスなら現在マスの経路数を足す
        if w + 1 < W and grid[h][w + 1] == ".":
            # modを取って更新
            dp[h][w + 1] += dp[h][w] % MOD_INT
        # 下が範囲内の空マスなら現在マスの経路数を足す
        if h + 1 < H and grid[h + 1][w] == ".":
            # modを取って更新
            dp[h + 1][w] += dp[h][w] % MOD_INT

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
G = []
mod = 10**9+7
for _ in range(H):
    G.extend([1 if a == '#' else 0 for a in input().strip()])
dp = [0]*(H*W)
for i in range(W):
    if G[i]:
        break
    dp[i] = 1

for i in range(W, H*W):
    if not G[i]:
        if i % W:
            dp[i] = (dp[i-1] + dp[i-W]) % mod
        else:
            dp[i] = dp[i-W]

print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
h,w = [int(i) for i in input().split()]
b = [input() for _ in range(h)]
MOD = 10**9+7
dp=[0]*w
dp[0]=1
for i in range(h):
    for j in range(w):
#        print(i,j)
        if b[i][j] == "#":
            dp[j] = 0
        elif j > 0:
            dp[j] += dp[j-1]
            dp[j] %= MOD
#    print(dp)
print(dp[w-1])

Submission status: Accepted

Solution code:
def h():
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]
    MOD = 10 ** 9 + 7
    memo = [[0] * W for _ in range(H)]
    memo[0][0] = 1
    for i in range(H):
        for j in range(W):
            if j + 1 < W and a[i][j + 1] == '.':
                memo[i][j + 1] += memo[i][j] % MOD
            if i + 1 < H and a[i + 1][j] == '.':
                memo[i + 1][j] += memo[i][j] % MOD
    return memo[-1][-1] % MOD


if __name__ == '__main__':
    ans = h()
    print(ans)

Submission status: Accepted

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

grid = [list(input()) for _ in range(h)]
mod = 10 ** 9 + 7

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            grid[i][j] = 1
            continue

        if grid[i][j] == "#":
            grid[i][j] = 0
            continue

        if i == 0:
            grid[i][j] = grid[i][j-1]
            continue

        if j == 0:
            grid[i][j] = grid[i-1][j]
            continue

        grid[i][j] = grid[i-1][j] + grid[i][j-1]

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
arr = []
for i in range(h):
    arr.append(input())
dp = [[0] * w for i in range(h)]
dp[0][0] = 1
for r in range(h):
    for c in range(w):
        if arr[r][c] == '.':
            if r > 0:
                dp[r][c] += dp[r - 1][c] if arr[r - 1][c] == '.' else 0
            if c > 0:
                dp[r][c] += dp[r][c - 1] if arr[r][c - 1] == '.' else 0
print(dp[h - 1][w - 1] % 1000000007)

Submission status: Accepted

Solution code:
md = 10 ** 9 + 7
h, w = map(int, input().split())
a = [input() for _ in range(h)]
t = [[1] * w for _ in range(h)]
for i, ai in enumerate(a):
    ti = t[i]
    for j, aij in enumerate(ai):
        if aij == "#":
            ti[j] = 0
        else:
            if j == 0:
                if i > 0:
                    ti[j] = t[i - 1][j]
            elif i == 0:
                if j > 0:
                    ti[j] = ti[j - 1]
            else:
                ti[j] = (ti[j - 1] + t[i - 1][j]) % md
print(t[-1][-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
h, w = [int(item) for item in input().split()]
field = []
for i in range(h):
    field.append(input().rstrip() + "#")
field.append("#" * (w+1))
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if field[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
        if field[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
print(dp[-1][-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

for r in range(1, H + 1):
    for c in range(1, W + 1):
        if r == 1 and c == 1:
            continue
        if a[r - 1][c - 1] == '#':
            continue
        else:
            dp[r][c] = (dp[r - 1][c] + dp[r][c - 1]) % MOD
print(dp[H][W])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

H, W = map(int, input().split())
A = [list(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 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[H - 1][W - 1] % mod)

Submission status: Accepted

Solution code:
# [int(e) for e in input().split()]
def sub():
    MOD = 10**9 + 7
    H, W = [int(e) for e in input().split()]
    mat = [[e for e in input()] for _ in range(H)]
    # print(mat)
    dp_table = [[0 for _ in range(W)] for _ in range(H)]
    dp_table[0][0] = 1
    for i in range(H):
        for j in range(W):
            # print(i,j)
            if mat[i][j] == "#":
                continue
            if i+1 < H:
                if mat[i+1][j] == ".":
                    dp_table[i+1][j] += dp_table[i][j]
                    if dp_table[i+1][j] > MOD:
                        dp_table[i+1][j] = dp_table[i+1][j] % MOD
            if j+1 < W:
                if mat[i][j+1] == ".":
                    dp_table[i][j+1] += dp_table[i][j]
                    if dp_table[i][j+1] > MOD:
                        dp_table[i][j+1] = dp_table[i][j+1] % MOD
    print(dp_table[H-1][W-1])



if __name__ == "__main__":
    sub()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    H, W = MI()
    grid = [input() for _ in range(H)]
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1
    for i in range(1, H):
        if grid[i][0] == ".":
            dp[i][0] = dp[i - 1][0]
    for j in range(1, W):
        if grid[0][j] == ".":
            dp[0][j] = dp[0][j - 1]

    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]
                dp[i][j] %= mod
    print(dp[H-1][W-1] % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

data = [[True for _ in range(W)] for _ in range(H)]
for h in range(H):
    S = input()
    for w, char in enumerate(S):
        if char == '#':
            data[h][w] = False

def isFloor(h, w):
    return 0 <= h < H and 0 <= w < W and data[h][w]

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 not isFloor(h, w):
            continue
        if isFloor(h-1, w) and isFloor(h, w-1):
            dp[h][w] = dp[h-1][w] + dp[h][w-1]
        elif isFloor(h-1, w):
            dp[h][w] = dp[h-1][w]
        elif isFloor(h, w-1):
            dp[h][w] = dp[h][w-1]
        dp[h][w] %= PRIME

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#") for x in range(h)]+[["#"]*(w+2)]
mod=10**9+7
dp=[[0]+[1]+[0]*w]+[(w+2)*[0] for i in range(h)]+[[0]*(w+2)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j]=="#":
            dp[i][j]=0
        else:
            dp[i][j]=sum(dp[i+s][j+t]%mod for s,t in ((0,-1),(-1,0)))%mod
print(dp[i][j]%mod)

Submission status: Accepted

Solution code:
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 y in range(h):
    for x in range(w):
        if A[y][x] == '#':
            continue
        if y != 0:
            dp[y][x] += dp[y-1][x]
        if x != 0:
            dp[y][x] += dp[y][x-1]
        dp[y][x] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
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 y in range(h):
    for x in range(w):
        if A[y][x] == '#':
            dp[y][x] = 0
        else:
            if y != 0:
                dp[y][x] += dp[y-1][x]
            if x != 0:
                dp[y][x] += dp[y][x-1]
            dp[y][x] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

h,w = map(int,input().split())
dp = [[0]*(w+1) for i in range(h+1)]
a = list(input() for _ in range(h))
dp[0][0] = 1
#配るDP
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])

Submission status: Accepted

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

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

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

for i in range(1, h):
    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]) % (10 ** 9 + 7)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        temp_field.append(0 if s == '.' else 1)
    field.append(temp_field)
    
dp = [[0] * (W + 1) for _ in range(H+1)]
dp[0][1] = 1

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
h, w = map(int, input().split())
dp = [[0 for i in range(w + 1)]for j in range(h + 1)]
a = [input()for _ in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      dp[i + 1][j + 1] = 0
    elif i == j == 0:
      dp[i + 1][j + 1] = 1
    else:
      dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % MOD
print(dp[h][w])

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
a = ['']*(H+2)
for h in range(H+2):
    if h == 0 or h == H+1:
        a[h] = '#'*(W+2)
    else:
        a[h] = '#' + input() + '#'
    
mod = 10**9+7
dp = [[0] * (W+2) for i in range(H+2)] #dp[h][w]
dp[1][1] = 1
dxy  = ([1,0],[0,1])

for i in range(1,H+1): 
    for j in range(1,W+1):
        for dx,dy in dxy:
            if a[i+dx][j+dy] == '.':
                dp[i+dx][j+dy] += dp[i][j]
                dp[i+dx][j+dy] %= mod

print(dp[H][W])

Submission status: Accepted

Solution code:
from functools import lru_cache

MOD = pow(10, 9) + 7

H, W = map(int, input().split())
A = [input() for _ in range(H)]
dp = [ [0 for j in range(W + 1)] for i in range(H + 1)]

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



print(dp[H][W])

Submission status: Accepted

Solution code:
def dp_solve(row, col):
    dp = [[0]*col for _ in range(row)]
    dp[0][0] = 1

    g = [input() for _ in range(row)]

    for i in range(row):
        for j in range(col):
            if dp[i][j] >= 10**9+7:
                dp[i][j] %= 10**9+7
            if j+1 < col and g[i][j+1] == '.':
                dp[i][j+1] += dp[i][j]
            if i+1 < row and g[i+1][j] == '.':
                dp[i+1][j] += dp[i][j]

    return dp[-1][-1]


if __name__ == "__main__":
    row, col = map(int, input().split())
    print(dp_solve(row, col))

Submission status: Accepted

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_h

H - Grid

"""
import collections
import functools
import sys

DIVISOR = 1000000007


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(grid):
    dp = collections.defaultdict(int)
    dp[0, 0] = 1

    for hh in range(H):
        for ww in range(W):
            if (hh, ww) == (0, 0):
                continue
            if grid[hh][ww] == "#":
                dp[hh, ww] = 0
            else:
                dp[hh, ww] = (dp[hh - 1, ww] + dp[hh, ww - 1]) % DIVISOR
    return dp[H - 1, W - 1]



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

grid = [input().strip() for _ in range(H)]
res = solve(grid)
print(res)

Submission status: Accepted

Solution code:
mod = 1000000007

def cnt(i,j):
  if (0 <= i-1 < H):
    dp[i][j] += dp[i-1][j]
  if (0 <= j-1 < W):
    dp[i][j] += dp[i][j-1]

H,W = list(map(int,input().split()))
grid = [[i for i in input()] for j in range(H)]

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

for h in range(H):
  for w in range(W):
    if grid[h][w] == ".":
      cnt(h,w)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = ["."+input() for _ in range(H)]
DP = [[0]*(W+1) for _ in range(H+1)]
DP[1][1] = 1
A = ["#"*W]+A
MOD = 10**9 + 7
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == ".":
            DP[i][j] += (DP[i-1][j]+DP[i][j-1])%MOD

print(DP[H][W])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[[0]*(m+1) for _ in range(n+1)]
dp[1][1]=1
grid=[]
grid.append(['0']*(m+1))
for i in range(n):
  grid.append(list('0'+input()))
for i in range(1,n+1):
  for j in range(1,m+1):
    tmp=0
    if grid[i-1][j] == '.':
      tmp+=dp[i-1][j]
    if grid[i][j-1] == '.':
      tmp+=dp[i][j-1]
    dp[i][j]+=tmp
print(dp[n][m]%(10**9+7))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
L=[]
for i in range(H):
    w=list(input())
    L.append(w)
    
ANS=[[0 for i in range(W)]for j in range(H)]
ANS[0][0]=1
for i in range(1,W):
    if L[0][i]=="#":
        ANS[0][i]=0
    else:
        ANS[0][i]=ANS[0][i-1]
for i in range(1,H):
    for j in range(W):
        if L[i][j]!="#":
            ANS[i][j]=0
            if j>0:
                ANS[i][j]+=ANS[i][j-1]
            ANS[i][j]+=ANS[i-1][j]
            ANS[i][j]%=(10**9+7)
print(ANS[H-1][W-1])

Submission status: Accepted

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

mod = 10**9+7
ij = [[H-1-1,W-1],[H-1,W-1-1]]
a[H-1][W-1] = 1
cnt = 0
while 1:
    i,j = ij[cnt]
    if a[i][j] == ".":
        a[i][j] = 0
        if type(a[i+1][j]) == int:
            a[i][j] += a[i+1][j]
        if type(a[i][j+1]) == int:
            a[i][j] += a[i][j+1]
        a[i][j] %= mod
        if i>0:
            ij.append([i-1,j])
        if j>0:
            ij.append([i,j-1])
    elif a[i][j] == "#":
        a[i][j] = 0
    cnt += 1
    if len(ij) <= cnt:
        break
if a[0][0] == ".":
    a[0][0] = 0
print(a[0][0])

Submission status: Accepted

Solution code:
from itertools import *
import sys
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=[[0]*(w+1) for _ in range(h+1)]
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:
        t[i+1][j+1]=1
    elif s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0
print(t[-1][-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [list(input()) + ['#'] for i in range(H)]
A.append(['#'] * (W + 1))
MOD = 10 ** 9 + 7

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

for h in range(H):
    for w in range(W):
        if A[h + 1][w] != '#':
            P[h + 1][w] += P[h][w]
            P[h + 1][w] %= MOD

        if A[h][w + 1] != '#':
            P[h][w + 1] += P[h][w]
            P[h][w + 1] %= MOD

print(P[-2][-2] % MOD)

Submission status: Accepted

Solution code:
#!/snap/bin/pypy3

MOD = 10 ** 9 + 7

def main():
    global MOD

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

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

    for i, line in enumerate(strings):
        for j, data in enumerate(line):
            if strings[i][j] == '#':
                continue
            dp[i+1][j+1] += dp[i][j+1] % MOD if dp[i][j+1] != '#' else 0
            dp[i+1][j+1] += dp[i+1][j] % MOD if dp[i+1][j] != '#' else 0


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

mod = pow(10,9)+7

r,c = list(map(int,input().split()))
arr = []
for i in range(r):
    string = input()
    lista = []
    for i in string:
        lista.append(i)
    arr.append(lista)

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

for i in range(r):
    if(arr[i][0] == '#'):
        break
    
    dp[i][0] = 1

for i in range(c):
    if(arr[0][i] == '#'):
        break
    dp[0][i] = 1

for i in range(1,r):
    for j in range(1,c):
        if(arr[i-1][j] == '.'):
            dp[i][j] += dp[i-1][j]
        if(arr[i][j-1] == '.'):
            dp[i][j] += dp[i][j-1]

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

Submission status: Accepted

Solution code:

mod = pow(10,9)+7
r,c = list(map(int,input().split()))
arr = []
for i in range(r):
    string = input()
    lista = []
    for i in string:
        lista.append(i)
    arr.append(lista)

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

for i in range(r):
    if(arr[i][0] == '#'):
        break
    dp[i][0] = 1
for i in range(c):
    if(arr[0][i] == '#'):
        break
    dp[0][i] = 1

for i in range(1,r):
    for j in range(1,c):
        if(arr[i-1][j] == '.'):
            dp[i][j] += dp[i-1][j]
        if(arr[i][j-1] == '.'):
            dp[i][j] += dp[i][j-1]


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

Submission status: Accepted

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    # input
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]

    MOD = 10**9 + 7

    # 0-indexed DPは0で初期化
    dp = [[0] * W for _ in range(H)]
    # DP初期条件
    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])

main()

Submission status: Accepted

Solution code:
mod = 10**9+7

h, w = map(int, input().split())
board = [list(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 board[i][j] == "#":
            continue
        if i != 0:
            dp[i][j] += dp[i-1][j]
        if j != 0:
            dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

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

dp[0][0] = 1
dirx = [0, 1]
diry = [1, 0]
for i in range(h):
    for j in range(w):

        for k in range(2):
            r = i + dirx[k]
            c = j + diry[k]

            if r < h and c < w and grid[r][c] == '.':
                dp[r][c] += dp[i][j]
                dp[r][c] %= int(1e9+7)

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