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:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

## a, bを無向辺として，隣接リストを作成
n, m = list(map(int, input().split()))
a = ["" for i in range(n)]

N = 10**9 + 7

for i in range(n):
    a[i] = str(input())

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

flag = 0
for i in range(n):
    if a[i][0] == "#" or flag == 1:
        dp[i][0] = 0
        flag = 1
    else:
        dp[i][0] = 1

flag = 0
for j in range(m):
    if a[0][j] == "#" or flag == 1:
        dp[0][j] = 0
        flag = 1
    else:
        dp[0][j] = 1

for i in range(1,n):
    for j in range(1,m):
        if a[i][j] == "#":
            dp[i][j] = 0
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % N

print(dp[n-1][m-1] % N)

Submission status: Accepted

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

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

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

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

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]
ans =dp[H-1][W-1]
ans = ans%((10**9)+7)
print(ans)

Submission status: Accepted

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

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

for x in range(1,W+1):
    for y in range(1,H+1):
        if x == y == 1:
            continue
        else:
            if A[y-1][x-1] != '#' and (dp[y-1][x] > 0 or dp[y][x-1] > 0):
                dp[y][x] = dp[y-1][x] + dp[y][x-1]
print(dp[H][W] % mod)

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 31/07/2020

from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

h, w = iia()
arr = []
for i in range(h):
    arr.append(list(is1()))
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 and j > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        elif i > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i - 1][j]
        elif j > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i][j - 1]
print(dp[-1][-1] % mod)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
M = 10**9 + 7
A = []
for _ in range(H):
  S = input()
  A.append(S)
L = [[0 for j in range(W)] for i in range(H)]
L[0][0] =  1
for i in range (H):
  for j in range (W):
    if A[i][j] == '.':
        if i > 0:
            L[i][j] += L[i-1][j] % M
        if j > 0:
            L[i][j] += L[i][j-1] % M
print(L[H-1][W-1] % M)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '#'*(W+2)
S[H+1] = '#'*(W+2)
for h in range(1,H+1):
  S[h] = '#' + input() + '#'
mod = 10**9+7
dp = [[0]*(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 h==1 and w==1:
      continue
    if S[h][w]=='#':
      continue
    dp[h][w] += dp[h][w-1]+dp[h-1][w]
    dp[h][w] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:

def mod(num):
    return num % (10 ** 9 + 7)

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

for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            dp[i][j] = -1

dp[0][0] = 1

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

for row in range(1, H):
    for col in range(W):
        if dp[row][col] != -1:
            if col == 0:
                dp[row][col] = dp[row - 1][col]
            else:
                dp[row][col] = mod(dp[row - 1][col] + dp[row][col - 1])
        else:
            dp[row][col] = 0

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

Submission status: Accepted

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
#= list(map(int, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

def mod(num):
    return num % (10 ** 9 + 7)

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

for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            dp[i][j] = -1

dp[0][0] = 1
for row in range(H):
    for col in range(W):
        if row != 0 or col != 0:
            if row == 0:
                if dp[row][col] != -1:
                    dp[row][col] = dp[row][col - 1]
                else:
                    dp[row][col] = 0
            elif col == 0:
                if dp[row][col] != -1:
                    dp[row][col] = dp[row - 1][col]
                else:
                    dp[row][col] = 0
            else:
                if dp[row][col] != -1:
                    dp[row][col] = mod(dp[row - 1][col] + dp[row][col - 1])
                else:
                    dp[row][col] = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 15:42:52 2020

@author: tinku
"""
def converter(arr,m,n):
    new_arr=[[0 for i in range(n)] for j in range(m)]
    for i in range(m):
        for j in range(n):
            if arr[i][j]=='.':
                new_arr[i][j]=0
            else:
                new_arr[i][j]=1
    return new_arr
            
m,n=map(int,input().split())
arr=[]
for i in range(m):
    arr.append(input())
arr=converter(arr,m,n)
if arr[0][0]==1 or arr[m-1][n-1]==1:
    print(0)
else:
    arr[0][0]=1
    for i in range(1,m):
        arr[i][0]=int(arr[i-1][0]==1 and arr[i][0]==0)
    for i in range(1,n):
        arr[0][i]=int(arr[0][i-1]==1 and arr[0][i]==0)
    for i in range(1,m):
        for j in range(1,n):
            if arr[i][j]==0:
                arr[i][j]=arr[i-1][j] + arr[i][j-1]
            else:
                arr[i][j]=0
    print((arr[m-1][n-1])%(10**9 +7))

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 i in range(h):
    for j in range(w):
        if i<h-1:
            if a[i+1][j]==".":
                dp[i+1][j]+=dp[i][j]
                dp[i+1][j]%=mod
        if j<w-1:
            if a[i][j+1]==".":
                dp[i][j+1]+=dp[i][j]
                dp[i][j+1]%=mod
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
NUM=10**9+7
H,W=list(map(int,input().split()))
matrix=[]
for i in range(H):
    matrix.append(list(input()))
dp=[[0]*W for i in range(H)]
dp[0][0]=1
for i in range(1,W):
    if(matrix[0][i]=='#'):
        dp[0][i]=0
    else:
        dp[0][i]=dp[0][i-1]
for j in range(1,H):
    if(matrix[j][0]=='#'):
        dp[j][0]=0
    else:
        dp[j][0]=dp[j-1][0]
for i in range(1,H):
    for j in range(1,W):
        if(matrix[i][j]=='#'):
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j] + dp[i][j-1])%NUM 
print(dp[H-1][W-1]%NUM)

Submission status: Accepted

Solution code:
from sys import stdin
h,w = map(int,stdin.readline().split())
arr = [list(stdin.readline()) 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 arr[i][j] == '.':
            dp[i][j] += (0 if i==0 else dp[i-1][j])+(0 if j==0 else dp[i][j-1])
            dp[i][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    dp = [[0 for _ in range(w)] for __ in range(h)]
    dp[0][0] = 1

    def calc(x, y, val):
        if x >= w or y >= h:
            return
        if mat[y][x] == "#":
            return
        dp[y][x] += val
        dp[y][x] %= MOD
        return

    for y in range(h):
        for x in range(w):
            calc(x + 1, y, dp[y][x])
            calc(x, y + 1, dp[y][x])
    print(dp[h - 1][w - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
A = [list(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):
    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] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
mod = 10**9 + 7
grid_0 = [0] * (W+1)
grid_0[1] = 1

for n in range(1,H+1):
  grid_1 = [0] * (W+1)
  for i, j in enumerate(input(), 1):
    if j == ".":
      grid_1[i] = (grid_0[i] + grid_1[i-1]) % mod
  grid_0 = grid_1

print(grid_0[-1])

Submission status: Accepted

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

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

for i in range(H):
  grid = input()
  if i == 0:
    Flag = True
    for j in range(W):
      if grid[j] == "#":
        Flag = False
      if Flag:
        dp[i][j] = 1
      else:
        dp[i][j] = 0
  else:
    for j in range(W):
      if grid[j] == "#":
        dp[i][j] = 0
      else:
        if j == 0:
          dp[i][j] = dp[i-1][j]
        else:
          dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
m = 10**9+7
index_lst = []
grid_0 = [0] * (W+1)
grid_0[1] = 1
for _ in range(1, H+1):
  grid_1 = [0] * (W+1)
  for i, j in enumerate(input(), 1):
    if j == '.':
      grid_1[i] = (grid_0[i] + grid_1[i-1]) % m
  grid_0 = grid_1
    
print(grid_0[-1])

Submission status: Accepted

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

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

D = [[0] * w for i in range(h)]
D[0][0] = 1
for i in range(h):
    for j in range(w):
        if (i!=0 or j!=0) and C[i][j]==".":
            if i-1 >= 0:
                D[i][j] += D[i-1][j]
            if j-1 >= 0:
                D[i][j] += D[i][j-1]
            D[i][j] %= mod
print(D[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]
    m = 10**9 + 7

    dp = [0] * W
    for i in range(H):
        for j in range(W):
            if i == j == 0:
                dp[j] = 1
                continue
            if a[i][j] == '.':
                if j > 0:
                    dp[j] = (dp[j] + dp[j-1]) % m
            else:
                dp[j] = 0
    print(dp[W-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    H,W=map(int,input().split())
    maze=[]
    for _ in range(H):
        a=input().rstrip()
        maze.append(a)
    path=[[0]*W for _ in range(H)]
    path[0][0]=1
    q=deque([[0,0]])
    finished=[[False]*W for _ in range(H)]
    while q:
        h,w=q.popleft()
        if finished[h][w]==True:
            continue
        for nh,nw in ([h+1,w],[h,w+1]):
            if nh<0 or nh>H-1 or nw<0 or nw>W-1:
                continue
            if maze[nh][nw]=="#":
                continue
            path[nh][nw]+=path[h][w]
            path[nh][nw]%=1000000007
            q.append([nh,nw])
        finished[h][w]=True
    print(path[-1][-1])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
r,c=map(int,input().split())
mod=10**9+7
g=[]
for _ in range(r):
  g.append(input())
dp=[[0 for j in range(c)] for i in range(r)]
dp[0][0]=1
for i in range(r):
  for j in range(c):
    if g[i][j]=='.':
        if i>0:
            dp[i][j]+=dp[i-1][j]%mod
        if j>0:
            dp[i][j]+=dp[i][j-1]%mod


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

Submission status: Accepted

Solution code:

def resolve():
    MOD = 10 ** 9 + 7
    H, W = map(int, input().split())
    G = [list(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 i + 1 < H and G[i + 1][j] == ".":
                dp[i + 1][j] += dp[i][j]
                dp[i + 1][j] %= MOD
            if j + 1 < W and G[i][j + 1] == ".":
                dp[i][j + 1] += dp[i][j]
                dp[i][j + 1] %= MOD
    print(dp[H-1][W-1])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
n, m = map(int, readline().split())
grid = []
for _ in range(n):
    row = readline()
    real_row = [c for c in row if c != "\n"]
    grid.append(real_row)
dp = []
sys.setrecursionlimit(10**7)

for _ in range(n):
    temp = []
    for j in range(m):
        temp.append(-1)
    dp.append(temp)


def traverse(i, j):
    path = 0
    if i < n-1 and j < m-1:
        if dp[i][j] != -1:
            return dp[i][j]
    if i == n - 1 and j == m - 1:
        return 1
    elif i == n - 1:
        if grid[i][j + 1] != "#":
            path += traverse(i, j + 1)
    elif j == m - 1:
        if grid[i + 1][j] != "#":
            path += traverse(i + 1, j)
    else:
        if grid[i + 1][j] != "#":
            path += traverse(i + 1, j)
        if grid[i][j + 1] != "#":
            path += traverse(i, j + 1)
    dp[i][j] = path
    return path % (10 ** 9 + 7)


print(traverse(0, 0))

Submission status: Accepted

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

H,W = map(int,readline().split())
DIV = 10 ** 9 + 7
G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

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

for i in range(H):
  for j in range(W):
    if G[i][j] == "#":
      dp[i + 1][j + 1] = 0
    else:
      dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
      dp[i + 1][j + 1] %= DIV
      
print(dp[-1][-1])

Submission status: Accepted

Solution code:
MOD = 1000000007
h,w=map(int,input().split())
graph=[]
for i in range(h):
  graph.append(list(input()))
#print(graph)
dp=[[0]*(w) for _ in range(h)]
dp[0][0]=1
for i in range(1,w):
  if graph[0][i]=='#':
    break
  dp[0][i]=1
for i in range(1,h):
  if graph[i][0]=='#':
    break
  dp[i][0]=1
for i in range(1,h):
  for j in range(1,w):
    #print(i-1,j-1)
    if(graph[i][j]=='#'):
      dp[i][j]=0
    else:
      dp[i][j]=(dp[i-1][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
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            if i < h - 1:
                dp[i+1][j] = dp[i][j]
            if j < w - 1:
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % 1000000007
print(dp[h-1][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]*1100 for _ in range(1100)]
dp[1][1] = 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if h == 1 and w == 1:
            continue
        if a[h-1][w-1] == '#':
            dp[h][w] = 0
        else:
            dp[h][w] += (dp[h-1][w] + dp[h][w-1]) % MOD
print(dp[H][W] % MOD)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=10**9+7
arr=[[1 for j in range(w)]for i in range(h)]
for i in range(h):
  string=input()
  for j in range(w):
    if string[j]=="#":
      arr[i][j]=0

dp=[[0 for j in range(w)]for i in range(h)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if i>0 and arr[i-1][j]:
      dp[i][j]=(dp[i][j]+dp[i-1][j])%m
    if j>0 and arr[i][j-1]:
      dp[i][j]=(dp[i][j]+dp[i][j-1])%m
print(dp[h-1][w-1]%m)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

for i in range(1, H):
    if A[i][0] == '.':
        dp[i][0] = dp[i - 1][0]

for j in range(1, W):
    if A[0][j] == '.':
        dp[0][j] = dp[0][j - 1]

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    H, W = map(int, input().split())
   
    dp = [[0]*W for i in range(H)]
    route = []
    for h in range(H):
        As = input().strip()
        route.append(As)

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                dp[h][w] = 1
                continue
            if h > 0 and route[h-1][w] != '#':
                dp[h][w] += dp[h-1][w]
            if w > 0 and route[h][w-1] != '#':
                dp[h][w] += dp[h][w-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
v=pow(10,9)+7
arr=[]
inp = list(map(int,input().split()))
row=inp[0]
col=inp[1]
for i in range(row):
    s=input()
    arr.append(s)
ans=[[0 for i in range(col)]for j in range(row)]
for i in range(col):
    if arr[0][i]=='#':
        break
    else:
        ans[0][i]=1
for i in range(row):
    if arr[i][0]=='#':
        break
    else:
        ans[i][0]=1
for i in range(1,row):
    for j in range(1,col):
        if arr[i][j]=='#':
            continue
        else:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1])%v
print (ans[-1][-1])

Submission status: Accepted

Solution code:
n , m = map(int , input().split())
dp = []
for i in range(n + 1):
    dp.append([])
    for j in range(m + 1):
        dp[i].append(0)
arr = []
for i in range(n):
    arr.append(input())
dp[1][1] = 1
for i in range(1,n + 1):
    for j in range(1,m + 1):
        if arr[i - 1][j - 1] == '#' or (i == 1 and j == 1):
            continue
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m] % 1000000007)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


# map(int, sys.stdin.read().split())


def input():
    return sys.stdin.readline().rstrip()


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

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

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

    pass


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = ['' for i in range(H)]
dp = [[1 for i in range(W)] for j in range(H)]

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

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

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

Submission status: Accepted

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

grid = []

for i in range(h):
    grid.append(input())

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

dp[0][0] = 1

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()

A_array = [ns() for _ in range(H)]

mod = 10 ** 9 + 7

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

ans[0][0] = 1
for i in range(1, W):
    if A_array[0][i] == "#":
        continue
    ans[0][i] = ans[0][i-1]

for i in range(1, H):
    if A_array[i][0] == "#":
        continue
    ans[i][0] = ans[i-1][0]


for i in range(1, H):
    for j in range(1, W):
        if A_array[i][j] == "#":
            continue
        ans[i][j] = (ans[i-1][j] + ans[i][j-1]) % mod

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
def main():
    MOD=10**9+7
    q=deque()
    H,W=tuple(map(int,sys.stdin.readline().split()))
    m,dp=[],[[0 for _ in range(W)] for _ in range(H)]
    for _ in range(H):m.append(list(sys.stdin.readline().strip()))
    dp[0][0]=1
    q.append((0,0))
    while len(q)>0:
        h,w=q.popleft()
        if h+1<H and m[h+1][w]=='.':  # down
            if dp[h+1][w]==0:q.append((h+1,w))
            dp[h+1][w]=(dp[h+1][w]+dp[h][w])%MOD
        if w+1<W and m[h][w+1]=='.':  # right
            if dp[h][w+1]==0:q.append((h,w+1))
            dp[h][w+1]=(dp[h][w+1]+dp[h][w])%MOD
    print(dp[H-1][W-1])
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
g = [list(input()) for _ in range(H)]
mod = int(1e9) + 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 g[i][j] == "#":
            continue
        if i + 1 < H:
            dp[i+1][j] += dp[i][j] % mod
        if j + 1 < W:
            dp[i][j+1] += dp[i][j] % mod
print(dp[H-1][W-1] % mod)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def main():
    MOD=10**9+7
    q=deque()
    H,W=tuple(map(int,sys.stdin.readline().split()))
    m=[]
    for _ in range(H):
        m.append(list(sys.stdin.readline().strip()))
    dp=[[0 for _ in range(W)] for _ in range(H)]
    dp[0][0]=1
    q.append((0,0))
    while len(q)>0:
        h,w=q.popleft()
        if h+1<H and m[h+1][w]=='.':  # down
            if dp[h+1][w]==0:q.append((h+1,w))
            dp[h+1][w]=(dp[h+1][w]+dp[h][w])%MOD
        if w+1<W and m[h][w+1]=='.':  # right
            if dp[h][w+1]==0:q.append((h,w+1))
            dp[h][w+1]=(dp[h][w+1]+dp[h][w])%MOD
    print(dp[H-1][W-1])
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import queue
INF=10**8
R=10**9+7
h,w=map(int,input().split())
maze=[input() for _ in range(h)]
d=[[0 for i in range(h)] for _ in range(w)]
sx=0
sy=0
gx=w-1
gy=h-1
q=queue.Queue()
dx=[1,0]
dy=[0,1]
q.put((sx,sy))
d[sy][sx]=1
while not q.empty():
  x,y=q.get()
  if (x,y)==(gx,gy):break
  for i in range(2):
    nx=x+dx[i]
    ny=y+dy[i]
    if nx<w and ny<h:
      if maze[ny][nx]=='.':
        if d[nx][ny]==0:
          q.put((nx,ny))
          d[nx][ny]=d[x][y]
        else:d[nx][ny]+=d[x][y]
print(d[gx][gy]%R)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x)


def solve(H, W, data):
    "void()"
    score = [[0] * (W + 1) for i in range(H + 1)]
    score[0][1] = 1
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            if data[y - 1][x - 1] == ord("#"):
                score[y][x] = 0
            else:
                score[y][x] = (score[y - 1][x] + score[y][x - 1]) % MOD
    # print(score)
    return score[H][W]


def main():
    H, W = map(int, input().split())
    data = [input() for i in range(H)]
    print(solve(H, W, data))


T1 = """
3 4
...#
.#..
....
"""

T2 = """
5 5
..#..
.....
#...#
.....
..#..
"""

T3 = """
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
"""

T4 = """
5 2
..
#.
..
.#
..
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    """


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    345263555
    """


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    24
    """


def _test():
    """
    >>> as_input(T1)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a=[input() for _ in range(H)]
MOD=10**9+7
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+1<H and a[i+1][j]=='.':
            dp[i+1][j]+=dp[i][j]
        if j+1<W and a[i][j+1]=='.':
            dp[i][j+1]+=dp[i][j]
        dp[i][j]%=MOD
print(dp[-1][-1])

Submission status: Accepted

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

H,W = map(int,readline().split())
G = [None] * (H + 1)
G[0] = "." * (W + 1)
for i in range(H):
  G[i + 1] = "." + readline().rstrip()

dp = [[0] * (W + 1) for i in range(H + 1)]
dp[1][0] = 1 # 便宜上、枠外に1を入れておくことで、dp[1][1]が1になる
DIV = 10 ** 9 + 7

for i in range(1, H + 1):
  for j in range(1, W + 1):
    if G[i][j] == "#":
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
      dp[i][j] %= DIV
      
print(dp[H][W])

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((h, w), dtype = np.int64)
dp[0][0] = 1
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
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 + 1 < H and maze[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j + 1 < W and maze[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
print(dp[H-1][W-1])