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:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)
# def solve():
# 	n, m = read()
# 	graph = [[] for i in range(n+1)]
# 	for _ in range(m):
# 		u, v = read()
# 		graph[u].append(v)
# 	visited = [0 for i in range(n+1)]
# 	def dfs(node):
# 		if visited[node]:
# 			return(visited[node])
# 		if not graph[node]:
# 			visited[node] = 0
# 			return(0)
# 		m = 0
# 		for i in graph[node]:
# 			m = max(m, dfs(i))
# 		visited[node] = 1 + m#ax(dfs(i) for i in graph[node])
# 		# print(node, visited[node])
# 		return(visited[node])

# 	ans = 0
# 	for i in range(1, n+1):
# 		ans = max(ans, dfs(i))
# 	# print(visited)
# 	print(ans)


def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	# dic = {}
	dp = [-1]*m*n
	# print(dp, len(dp))
	def count_paths(i, j):
		# key = str(i)+"-"+str(j)
		# if key in dic:
		# 	return(dic[key])
		key = (i*m + j)
		# print(key)
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	# print(dp, len(dp))
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		# key = (i*m + j)
		# print(key)
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	# solve()
	grid()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
l=input().split()
r=int(l[0])
c=int(l[1])
l=[]
for i in range(r):
	s=input()
	l.append(s)
dp=[[0 for i in range(c)]for i in range(r)]
dp[0][0]=1
for i in range(1,r):
	if(l[i][0]=='#'):
		dp[i][0]=0
		continue
	dp[i][0]=dp[i-1][0]
for j in range(1,c):
	if(l[0][j]=='#'):
		dp[0][j]=0
		continue
	dp[0][j]=dp[0][j-1]
for i in range(1,r):
	for j in range(1,c):
		if(l[i][j]=='#'):
			dp[i][j]=0
		else:
			dp[i][j]=dp[i-1][j]+dp[i][j-1]
			dp[i][j]%=1000000007
print(dp[r-1][c-1])

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    modulo = 10**9+7
    board = []
    for _ in range(H):
        board.append(input().strip())
    count = [[0]*W for _ in range(H)]
    count[0][0] = 1
    for i in range(H):
        for j in range(W):
            if board[i][j] == '.':
                if j > 0 and board[i][j-1] == '.':
                    count[i][j] = (count[i][j]+count[i][j-1])%modulo
                if i > 0 and board[i-1][j] == '.':
                    count[i][j] = (count[i][j]+count[i-1][j])%modulo
    return count[-1][-1]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

h, w = map(int, rl().split())

li = []
dh = [0, -1]
dw = [-1, 0]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
for _ in range(h):
    li.append(rl().rstrip())
for i in range(h):
    for j in range(w):
        if li[i][j] == '#':
            continue
        a = 0
        for k in range(2):
            nh = i + dh[k]
            nw = j + dw[k]
            if nh < 0 or nw < 0:
                continue
            a += dp[nh][nw]
        if dp[i][j] == 0:
            dp[i][j] = a
print((dp[-1][-1]) % (10**9 + 7))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            continue
        if i>=1:
            dp[i][j]+=dp[i-1][j]
        if j>=1:
            dp[i][j]+=dp[i][j-1]
        dp[i][j]%=mod
print(dp[-1][-1])

Submission status: Accepted

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

dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[i][1] == "#":
        addi = 0
    dp[i][1] += addi
addi = 1
for i in range(2,w+1):
    if a[1][i] == "#":
        addi = 0
    dp[1][i] += addi


for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "#":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])
#for i in range(h+2):
#    print(dp[i])

Submission status: Accepted

Solution code:
def add(a, b):
    mod = 1e9+7
    c = a + b
    if c >= mod:
        c -= mod
    return c

H, W = [int(x) for x in input().split()]

sl = [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):
        for frm in [[i-1, j], [i, j-1]]:
            r, c = frm
            if r >= 0 and c >= 0 and sl[r][c] != '#':
                dp[i][j] = add(dp[i][j], dp[r][c])

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


"""
using ll = long long; 
int add(int a, int b) {
    int MOD = 1e9 + 7;
    return (a + b) % MOD;
}
int main() {
    int H;
    int W;
    scanf("%d%d\n", &H, &W);
    vector<vector<int>> dp(H, vector<int>(W));
    vector<vector<bool>> is_wall(H, vector<bool>(W));
    for (int i = 0; i < H; i++) {
        scanf("\n");
        for (int j = 0; j < W; j++) {
            char ch;
            scanf("%c", &ch);
            //cout << i << " " << j << " " << ch << endl;
            if (ch == '#') {
                is_wall[i][j] = true;
            }
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            //cout << i << " " << j << " " << is_wall[i][j] << endl;
            if (!is_wall[i][j]) {
                if (i - 1 >= 0) {
                    dp[i][j] = add(dp[i][j], dp[i-1][j]);
                }
                if (j - 1 >= 0) {
                    dp[i][j] = add(dp[i][j], dp[i][j-1]);
                }    
            }
        }
    }    
	printf("%d\n", dp[H-1][W-1]);
	return 0;
}



"""

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dp = [[f_inf] * W for _ in range(H)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if A[h][w] != "#":
                if h - 1 >= 0 and w - 1 >= 0:
                    dp[h][w] = min(dp[h][w], ((dp[h - 1][w] if A[h - 1][w] == "." else 0) + (dp[h][w - 1] if A[h][w - 1] == "." else 0)) % mod)
                elif h - 1 >= 0:
                    dp[h][w] = min(dp[h][w], (dp[h - 1][w] if A[h - 1][w] == "." else 0) % mod)
                elif w - 1 >= 0:
                    dp[h][w] = min(dp[h][w], (dp[h][w - 1] if A[h][w - 1] == "." else 0) % mod)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from functools import lru_cache
from collections import deque

#input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 5)

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[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])
#print(dp)

Submission status: Accepted

Solution code:
H,W = [int(i) for i in input().split()]
grid = [input() for i in range(H)]
dp = [[0]*(W+1) for i in range(H+1)]
for i in range(1,H+1):
    for j in range(1,W+1):
        if grid[i-1][j-1] == ".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if i == j == 1:
            dp[i][j] = 1
print(dp[-1][-1]%(10**9+7))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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
dp[1][1] = 1
for i in range(H):
    for j in range(W):
        if i==j and i==0:continue
        if A[i][j]=='.':
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            dp[i+1][j+1] %= MOD

print(dp[H][W])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
maze = [input() for _ in range(N)]
dp = [[0]*M for _ in range(N)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(M):
        if maze[i][j] != "#":
            if i-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = [input() for i in range((H))]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
m = 10**9 + 7
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            continue
        if i >= 1:
            dp[i][j] += dp[i-1][j]
        if j >= 1:
            dp[i][j] += dp[i][j-1]

        dp[i][j] %= m

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            continue
        if i >= 1:
            dp[i][j] += dp[i - 1][j]
        if j >= 1:
            dp[i][j] += dp[i][j - 1]
        dp[i][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def grid(mat: list):
    m = len(mat)
    n = len(mat[0])
    dp = [[0 for _ in range(n)] for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if mat[i][j] == '.':
                if i > 0:
                    dp[i][j] = dp[i - 1][j]
                if j > 0:
                    dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]%1000000007


if __name__ == '__main__':
    m, n = list(map(int, input().split()))
    mat = [[]] * m
    for i in range(m):
        mat[i] = [c for c in input()]
    print(grid(mat))

Submission status: Accepted

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

mat = []
dp = []
m = 10**9+7

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

dp[0][0] = 1


for x in range(h):
    for y in range(w):

        if x != 0 or y != 0:
            if mat[x][y] == "#":
                dp[x][y] = 0

            else:
                dp[x][y] = (dp[x - 1][y] + dp[x][y - 1]) % m

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

Submission status: Accepted

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

mat = []
dp = []
m = 10**9+7

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

dp[0][0] = 1


for x in range(h):
    for y in range(w):

        if x != 0 or y != 0:
            if mat[x][y] == "#":
                dp[x][y] = 0

            else:
                dp[x][y] += (dp[x - 1][y] + dp[x][y - 1]) % m

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

Submission status: Accepted

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

z = []
p = []
m = 10**9+7
for i in range(h):
    z.append(list(input()))
    p.append(list([0]*w))
p[0][0] = 1

for x in range(h):
    for y in range(w):
        if x != 0 or y != 0:
            if z[x][y] == "#":
                p[x][y] == 0
            else:
                p[x][y] += (p[x-1][y] + p[x][y-1])%m
               
                
print(p[h-1][w-1])

Submission status: Accepted

Solution code:
mod = 10**9+7


def main():
    H, W = map(int, input().split())
    a = [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 i != 0 or j != 0:
                if a[i][j] == ".":
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                    dp[i][j] %= mod
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7


def main():
    H, W = map(int, input().split())
    a = [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 a[i][j] == ".":
                if j+1 < W:
                    dp[i][j + 1] += dp[i][j]
                    dp[i][j+1] %= mod
                if i+1 < H:
                    dp[i + 1][j] += dp[i][j]
                    dp[i+1][j] %= mod
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m,mod=[],10**9+7
for i in range(h):m.append(input())
dp=[[0]*w for i in range(h)]
dp[0][0]=1
for i in range(h):
	for j in range(w):
		if m[i][j]=='.':
			if i==0 and j!=0:dp[i][j]=dp[i][j-1]
			elif i!=0 and j==0:dp[i][j]=dp[i-1][j]
			elif i!=0 and j!=0: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())
grid = []
for h in range(H):
  S = input()
  tmp = []
  for s in S:
    tmp.append(s)
  grid.append(tmp)


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

for h in reversed(range(H)):
  for w in reversed(range(W)):
    if (h+1) <= (H-1):
      dp[h][w] += dp[h+1][w]
    if (w+1) <= (W-1):
      dp[h][w] += dp[h][w+1]
    if grid[h][w] == "#":
      dp[h][w] = 0
    
      
print(dp[0][0] % (10**9 + 7))

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
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)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

H,W = MI()
V = [list(ST()) for _ in range(H)]
dp = FILL2(0,H+1,W+1)
dp[1][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        if V[i-1][j-1] == '.' and (i!=1 or j!=1):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD
print(dp[H][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
mod=10**9+7
chk=[[0] for f in range(H)]
ans=[[0 for e in range(W)] for f in range(H)]
ans[0][0]=1
for i in range(H):
 chk[i]=[d for d in input()]
for i in range(1,W):
 if chk[0][i]==".":
  ans[0][i]=ans[0][i-1]
for i in range(1,H):
 if chk[i][0]==".":
  ans[i][0]=ans[i-1][0]
for i in range(1,H):
 for j in range(1,W):
  if chk[i][j]==".":
   ans[i][j]=ans[i-1][j]+ans[i][j-1]
   ans[i][j]%=mod
print(ans[H-1][W-1])

Submission status: Accepted

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

H, W = map(int, input().split())
a = [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 a[i][j]=='#':
            continue
        
        if i-1>=0:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= MOD
        
        if j-1>=0:
            dp[i][j] += dp[i][j-1]
            dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	rows, cols = rli()
	dp = [[0 for __ in range(cols)] for _ in range(rows)]
	A = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "#":
				row.append(1)
			else:
				row.append(0)
		A.append(row)

	dp[0][0] = 1
	for c in range(1, cols):
		if A[0][c] == 1:continue
		dp[0][c] = dp[0][c-1]

	for r in range(1, rows):
		if A[r][0] == 1: continue
		dp[r][0] = dp[r-1][0]

	for r in range(1, rows):
		for c in range(1, cols):
			if A[r][c] == 1: continue
			dp[r][c] = dp[r-1][c] + dp[r][c-1]

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

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
mod=round(1e9+7)

r,c = list(map(int, input().split()))
mat = []
for i in range(r):
    mat.append(list(input()))
dp=[]
for i in range(r):
    dp.append([0]*(c))
for i in range(r):
    if mat[i][0]=='#':
        break
    else:
        dp[i][0]=1
for i in range(c):
    if mat[0][i]=='#':
        break
    else:
        dp[0][i]=1
for i in range(1,r):
    for j in range(1,c):
        if mat[i][j]=='#':
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[r-1][c-1])

Submission status: Accepted

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

Submission status: Accepted

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

a = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

# print(a)
# print(dp)

dp[0][0] = 1

for i in range(H): #行
    for j in range(W): #列
        if a[i][j] == "#" or (i == H-1 and j == W-1):
            continue

        if i == H-1:
            if a[i][j+1] != "#":
                dp[i][j+1] += dp[i][j]
        elif j == W-1:
            if a[i+1][j] != "#":
                dp[i+1][j] += dp[i][j]
        else:
            if a[i][j+1] != "#":
                dp[i][j+1] += dp[i][j]
            if a[i+1][j] != "#":
                dp[i+1][j] += dp[i][j]

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

itta=[[0]*w for i in range(h)]
itta[0][0]=1
d=deque([[0,0]])
while d:
    nh,nw=d.popleft()
    itta[nh][nw]%=mod
    if nh+1<h and a[nh+1][nw]==".":
        if itta[nh+1][nw]==0:
            d.append([nh+1,nw])
        itta[nh+1][nw]+=itta[nh][nw]
    if nw+1<w and a[nh][nw+1]==".":
        if itta[nh][nw+1]==0:
            d.append([nh,nw+1])
        itta[nh][nw+1]+=itta[nh][nw]

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
dp=[]
mod=10**9+7
for _ in range(n):
    s.append(input())
    dp.append([0]*m)

for i in range(n):
    for j in range(m):
        if i==0 and j==0:
            dp[i][j]=1 
        else:
            if s[i][j]=='#':
                dp[i][j]=0
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[n-1][m-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
grid=[list(input()) for i in range(n)]
ans=[[0]*m for i in range(n)]
mod=10**9 +7
ans[0][0]=1
for i in range(1,n):
    if grid[i][0]=='.':
        ans[i][0]=ans[i-1][0]
for i in range(1,m):
    if grid[0][i]=='.':
        ans[0][i]=ans[0][i-1]


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


print(ans[n-1][m-1]%mod)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    A=[input() for _ in range(h)]
    dp=[[0]*w for _ in range(h)] #(i,j)までの経路の総数
    dp[0][0]=1
    mod=10**9+7
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":continue
            if i>=1 and j>=1:    
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%mod
            elif j==0:
                dp[i][j]+=dp[i-1][j]%mod
            else:
                dp[i][j]+=dp[i][j-1]%mod
    print(dp[-1][-1]%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    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 i in range(h):
        for j in range(w):
            if A[i][j]=="#":continue
            if i>=1 and j>=1:    
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%mod
            elif j==0:
                dp[i][j]+=dp[i-1][j]%mod
            else:
                dp[i][j]+=dp[i][j-1]%mod
    print(dp[-1][-1]%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
mod=1000000007
n,m=map(int,input().split())
ll=[]
dp=[]
for i in range(n):
  s=input()
  ll.append(s)
  l=[0]*m
  dp.append(l)
for i in range(n):
  if(ll[i][0]=='#'):
    break
  dp[i][0]=1
for j in range(m):
  if(ll[0][j]=='#'):
    break
  dp[0][j]=1
for i in range(1,n):
  for j in range(1,m):
    if(ll[i][j]!='#'):
    	dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[n-1][m-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす
mod = 1000000007

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    H, W = map(int, input().rstrip().split())
    maps = []
    for _ in range(H):
        line = input().rstrip()
        maps.append(line)

    # 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 == 0 and j == 0) or maps[i][j] == "#":
                continue
            tmp = 0
            if i - 1 >= 0 and maps[i-1][j] == ".":
                tmp += dp[i-1][j]
                tmp %= mod
            if j - 1 >= 0 and maps[i][j-1] == ".":
                tmp += dp[i][j-1]
                tmp %= mod
            dp[i][j] = tmp
    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if i == j == 1:
            dp[i][j] = 1
        elif maze[i - 1][j - 1] == ".":
            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().strip().split())
grid = []
for i in range(n):
    grid.append(input())
dp = [[None]*m for _ in range(n)]
dp[n-1][m-1] = 1
for i in range(n-2, -1, -1):
    if grid[i][m-1] == '.':
        dp[i][m-1] = dp[i+1][m-1]
    else:
        dp[i][m-1] = 0
for j in range(m-2, -1, -1):
    if grid[n-1][j] == '.':
        dp[n-1][j] = dp[n-1][j+1]
    else:
        dp[n-1][j] = 0
for i in range(n-2, -1, -1):
    for j in range(m-2, -1, -1):
        if grid[i][j] == '.':
            dp[i][j] = (dp[i+1][j] + dp[i][j+1])%(10**9 + 7)
        else:
            dp[i][j] = 0
print(dp[0][0])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    mod = 10**9 + 7
    H, W = geta(int)
    g = []
    for _ in range(H):
        g.append(gete())

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

    for i in range(W):
        if g[0][i] == "#": break
        dp[0][i] = 1

    for i in range(H):
        if g[i][0] == "#": break
        dp[i][0] = 1

    for i, gi in enumerate(g[1:], 1):
        for j, gij in enumerate(gi[1:], 1):
            if gij == "#":
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    mod = 10**9 + 7
    H, W = geta(int)
    g = []
    for _ in range(H):
        g.append(gete())

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

    for i, gi in enumerate(g):
        if i == 0:
            w = gi.index("#") if "#" in gi else W
            dp[0] = [1 if j < w else 0 for j in range(W)]
        else:
            for j, gij in enumerate(gi):
                if gij == "#":
                    dp[i][j] = 0
                else:
                    dp[i][j] = (dp[i - 1][j] +
                                (dp[i][j - 1] if j > 0 else 0)) % mod

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = ["#"*(w+1)]
for _ in range(h):
    x = input()
    x = "#" + x
    grid.append(x)
p = 10**9 + 7
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] =1
for i in range(h):
    for j in range(w):
        if grid[i][j+1] == ".":
            dp[i+1][j+1] += dp[i][j+1]
            dp[i+1][j+1] %= p
        if grid[i+1][j] == ".":
            dp[i+1][j+1] += dp[i+1][j]
            dp[i+1][j+1] %= p
print(dp[h][w])

Submission status: Accepted

Solution code:
large_p = 10**9 + 7
def main():
    h, w = map(int, input().split())
    grid = [tuple(map(str, input())) for _ in range(h)]
    grid_root = [[0] * w for _ in range(h)]

    # 最もうえの行に「そのセルにいける場合の数」をいれる。右へ進み続けるしかないので１か０。
    flag = 1
    for i1 in range(w):
        if grid[0][i1] == '#':
            flag = 0
        grid_root[0][i1] += flag

    flag = 1
    for i2 in range(h):
        if grid[i2][0] == '#':
            flag = 0
        grid_root[i2][0] += flag
    for j1 in range(1, h):
        for j2 in range(1, w):
            if grid[j1][j2] == '.':
                grid_root[j1][j2] = grid_root[j1-1][j2] + grid_root[j1][j2-1]
    print(grid_root[h-1][w-1] % large_p)

if __name__ == '__main__':
    main()