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:
MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]

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


for i in range(1, H):
    for j in range(1, W):
        if G[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:
from collections import deque

MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]


def main():
    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if G[i][0] == '#':
            break
        dp[i][0] = 1
    for i in range(W):
        if G[0][i] == '#':
            break
        dp[0][i] = 1

    que = deque([(0, 0)])

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (0, 1)):
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '#':
                continue
            if nh > 0 and nw > 0:
                if dp[nh][nw]:
                    continue
                dp[nh][nw] = (dp[nh - 1][nw] + dp[nh][nw - 1]) % MOD
            que.append((nh, nw))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

MOD = 10**9 + 7
H, W = map(int, input().split())
G = [input() for _ in range(H)]


def main():
    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 0

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

    que = deque([(0, 0)])

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (0, 1)):
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '#':
                continue
            if dist[nh][nw] != -1:
                continue
            if nh > 0 and nw > 0:
                dp[nh][nw] = (dp[nh - 1][nw] + dp[nh][nw - 1]) % MOD
            dist[nh][nw] = dist[h][w] + 1
            que.append((nh, nw))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

MOD = 10**9+7

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

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

for j in range(W):
    if a[0][j] == '.':
        dp[0][j] = 1
    else :
        break

for i in range(H):
    for j in range(W):
        if i != 0  or j != 0:
            if a[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())
l = [['#']*(w+2)]
for i in range(h):
    l.append(['#']+list(input())+['#'])
l.append(['#']*(w+2))

mod = 10**9+7
dp = [[0]*(w+2) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            dp[1][1] = 1
            continue
        if l[i][j] == '.':
            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
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

mod = 10**9 + 7

H, W = inpl()
a = []
for i in range(H):
    a.append(input().strip())

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

mod = 10**9 + 7

H, W = inpl()
a = []
flag = [[False] * W for i in range(H)]
for i in range(H):
    a.append(input().strip())
_debug(a)
dp = [[0] * (W+1) for i in range(H+1)]
dp[0][0] = 1

for i in range(max(H, W)):
    if i < H:
        for j in range(W):
            if a[i][j] == "#" or flag[i][j]:
                continue
            flag[i][j] = True
            for x, y in ((0, 1), (1, 0)):
                dp[i+x][j+y] += dp[i][j]
                dp[i+x][j+y] %= mod
    if i < W:
        for j in range(H):
            if a[j][i] == "#" or flag[j][i]:
                continue
            flag[j][i] = True
            for x, y in ((0, 1), (1, 0)):
                dp[j+x][i+y] += dp[j][i]
                dp[j+x][i+y] %= mod
    
print(dp[H-1][W-1])

Submission status: Accepted

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

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

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
      continue
    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
    dp[i + 1][j + 1] %= DIV
    
print(dp[-1][-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [[a for a in input()] for _ in range(H)]
mod = 10 ** 9 + 7
DP = [[0] * (W + 1) for _ in range(H+1)]
DP[1][1] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i-1][j-1] == '#':
            continue
        if i == 1 and j == 1:
            continue
        DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
        DP[i][j] %= mod

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(input())
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:
      if j == 0:
        continue
      else:
        if S[i][j] == ".":
          dp[i][j] = dp[i][j-1]
    else:
      if S[i][j] == ".":
        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[H-1][W-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().strip().split())
grid = [list(input()) for i in range(H)]
dp = [[0 for i in range(W+1)] for i in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i][j+1] += dp[i][j]
        dp[i][j] = dp[i][j]%(1000000007)
print(dp[H-1][W-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin 
import math 

def main():

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

	grid = []

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


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

	L[0][0] = 1

	for h_ind in range(h):
		for w_ind in range(w):
			if grid[h_ind][w_ind] == '.':
				if h_ind - 1 >= 0:
					L[h_ind][w_ind] += L[h_ind - 1][w_ind]
				if w_ind - 1 >= 0:
					L[h_ind][w_ind] +=  L[h_ind][w_ind - 1]


	modulo = int (pow(10, 9) + 7)
	print(L[h - 1][w - 1] % modulo)











if __name__ == '__main__':
	main()

Submission status: Accepted

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

def main():
    MOD = 10 ** 9 + 7
    h, w = map(int, input().split())
    tizu = [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 tizu[i][j] == "#":
                continue
            if i != 0:
                dp[i][j] += dp[i - 1][j]
            if j != 0:
                dp[i][j] += dp[i][j - 1]
            dp[i][j] %= MOD
    print(dp[-1][-1])
main()

Submission status: Accepted

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

field = []

for _ in range(H):
    field.append(input())

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

# dp[h][w] = マス[1, 1]からマス[h, w]までの太郎くんの経路のそうパターン数。ans = dp[H-1][W-1]

for h in range(H):
    for w in range(W):
        if field[h][w] == '#': continue

        if h-1 >= 0 and field[h-1][w] == ".":
            dp[h][w] += dp[h-1][w]

        if w-1 >= 0 and field[h][w-1] == '.':
            dp[h][w] += dp[h][w-1]

        dp[h][w] %= 1000000007

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

Submission status: Accepted

Solution code:
# H - Grid 1
H,W = map(int,input().split())
maze = []
for _ in range(H):
    a = list(input())
    maze.append(a)

# dp[i][j]: 座標 (i, j) に到達できる経路の数
dp = [[0]*(W) for _ in range(H)]

# 初期条件 
# 座標 (0, 0) への経路は 1 通り
dp[0][0] = 1

for h in range(H):
    for w in range(W):
        # スタート位置のときはスルー
        if (h,w) == (0,0):
            continue
        # 壁があるときはスルー
        if maze[h][w] == '#':
            continue
        # 左にマスがあるとき 
        if w > 0:
            dp[h][w] = (dp[h][w] + dp[h][w-1])%(10**9+7)
        # 上にマスがあるとき
        if h > 0:
            dp[h][w] = (dp[h][w] + dp[h-1][w])%(10**9+7)
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
for _ in range(h):
  a.append(list(input()))
#print(a)
dp=[[0 for _ in range(w)] for _ in range(h)]
dp[0][0]=1
#print(dp)
MOD=10**9+7
for i in range(h):
  for j in range(w):
    #print(i,j)
    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)
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
arr=[] 
n,m=map(int,input().split()) 
dp=[[0 for j in range(m)] for i in range(n)] 
for i in range(n):
	arr.append(input()) 
dp[0][0]=1 
for i in range(1,n):
	if arr[i][0]!='#':
		dp[i][0]+=dp[i-1][0]
	else:
		break  
for i in range(1,m):
	if arr[0][i]!='#':
		dp[0][i]+=dp[0][i-1]
	else:
		break 


for i in range(1,n):
	for j in range(1,m):
		if arr[i][j]!='#':
			dp[i][j]=dp[i-1][j]+dp[i][j-1]  
mod=10**9+7 
print(dp[-1][-1]%mod)

Submission status: Accepted

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

s=[input() for _ in range(h)]

ans=[[0]*w for _ in range(h)]
for i in range(w):
    if s[0][i]=='#' :
        break
    ans[0][i]=1
for j in range(h):
    if s[j][0]=='#' :
        break
    ans[j][0]=1

for i in range(1,h):
    for j in range(1,w):
        if s[i][j]=='#':
            ans[i][j]=0
        else:
            ans[i][j]=ans[i][j-1]+ans[i-1][j]

print(ans[h-1][w-1]%(1000000000+7))

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
h,w = ip()
grid = [input().strip() 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 >= 0 and grid[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if j-1 >= 0 and grid[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]
        dp[i][j] %= M
print(dp[-1][-1]%M)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 10**9+7
h,w = ip()
grid = [input().strip() 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 >= 0 and grid[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if j-1 >= 0 and grid[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]
print(dp[-1][-1]%M)

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 w in range(1, W):
    if a[0][w]=='#': break
    dp[0][w] = 1
for h in range(1, H):
    if a[h][0]=='#': break
    dp[h][0] = 1
for h in range(1, H):
    for w in range(1, W):
        if a[h][w]=='#': continue
        dp[h][w] = (dp[h-1][w]+dp[h][w-1])%mod
print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    # もらうDP
    H, W = (int(i) for i in input().split())
    c = [input() for i 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):
            le = 0
            up = 0
            if 0 <= w - 1 and c[h][w-1] != "#":
                le = dp[h][w-1]
            if 0 <= h - 1 and c[h-1][w] != "#":
                up = dp[h-1][w]
            dp[h][w] += le + up
            dp[h][w] %= MOD
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dist = [[-1]*W for i in range(H)]

    def bfs_2d(sy=0, sx=0):
        que = deque()

        dist[sy][sx] = 1
        que.append((sy, sx))
        d = ((0, 1), (1, 0))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    dist[next_h][next_w] += dist[uh][uw]
                    dist[next_h][next_w] %= MOD
                    continue
                if c[next_h][next_w] == '#':
                    continue
                dist[next_h][next_w] = dist[uh][uw]
                dist[next_h][next_w] %= MOD
                que.append((next_h, next_w))

    bfs_2d()
    print(dist[H-1][W-1] if dist[H-1][W-1] != -1 else 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 7
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 + 1 < H and a[i + 1][j] == '.':
            dp[i + 1][j] = dp[i][j] + dp[i + 1][j]
            dp[i + 1][j] %= INF
        if j + 1 < W and a[i][j + 1] == '.':
            dp[i][j + 1] = dp[i][j + 1] + dp[i][j]
            dp[i][j + 1] %= INF

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

Submission status: Accepted

Solution code:
INF=float('inf')
mod=10**9+7

h,w=map(int,input().split())
G=[]
for _ in range(h):
  s=input()
  G.append(s)
  
dp=[[-INF for i in range(w+1)] for j in range(h+1)]
dp[1][1]=1

for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i-1][j-1]=='#':
      continue
    if i==1 and j==1:
      continue
    dp[i][j]=max(0,dp[i-1][j])+max(0,dp[i][j-1])
    dp[i][j]%=mod
print(dp[h][w])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp,visited
    if visited[y][x]:
        return dp[y][x]
    else:
        visited[y][x]=True
        if mp[y][x]!='#' and dp[y][x]==0:
            dp[y][x]=(grid(y-1,x)+grid(y,x-1))%mod
        return dp[y][x]

H,W=map(int,input().split())
mp=[['#']*(W+1)]
for _ in range(H):
    mp.append(['#']+list(input()))

dp=[[0]*(W+1)for _ in range(H+1)]
dp[1][1]=1
visited=[[False]*(W+1)for _ in range(H+1)]
mod=10**9+7
grid(H,W)
print(dp[H][W])

Submission status: Accepted

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

def grid(y,x,mp):
    mod=10**9+7
    dp=[[0]*x for _ in range(y)]
    dp[0][0]=1
    for h in range(y):
        for w in range(x):
            if mp[h][w]=='.':
                if 1<=h<y and 1<=w<x:
                    dp[h][w]=((dp[h][w-1]+dp[h-1][w])%mod)
                elif h==0 and 1<=w<x:
                    dp[h][w]=(dp[h][w-1]%mod)
                elif 1<=h<y and w==0:
                    dp[h][w]=(dp[h-1][w]%mod)
    return dp[y-1][x-1]


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

Submission status: Accepted

Solution code:
def solve(H, W, a):
    mod = 10 ** 9 + 7

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

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

    return dp[H-1][W-1]


if __name__ == "__main__":
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]

    print(solve(H, W, a))

Submission status: Accepted

Solution code:
def grid(maze,h,w):
    mod = 7+10**9
    visited = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                continue

            if i==0 and j==0:
                visited[i][j] = 1
                
            
            elif i == 0:
                visited[i][j] = visited[i][j-1]
            elif j == 0:
                visited[i][j] = visited[i-1][j]
            else:
                visited[i][j] = (visited[i-1][j]%mod + visited[i][j-1]%mod)%mod
    
    return visited[h-1][w-1]


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

maze = []

for _ in range(h):
    maze.append(list(input()))

print(grid(maze,h,w))

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)



def solve():
    h,w=sep()
    N=10**9 +7
    ar=[]
    for i in range(h):
        ar.append([i for i in inp().strip()])
    dp=[[0 for i in range(w+5)] for _ in range(h+5)]
    dp[0][0]=1
    for i in range(1,h):
        if ar[i][0]==".":
            dp[i][0]=1
        else:
            break
    for i in range(1,w):
        if ar[0][i]==".":
            dp[0][i]=1
        else:
            break
    for i in range(1,h):
        for j in range(1,w):
            if ar[i][j]=="#":
                dp[i][j]=0
                continue
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%N

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


solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
from sys import setrecursionlimit

setrecursionlimit(1000000)


INF = float("inf")

d = deque()
# ---Input---#
# n = int(input())
h, w = map(int, input().split())

a = [["#" for _ in [INF] * (w + 1)] for _ in [INF] * ((h + 1))]
memo = [[0 for _ in [INF] * (w + 1)] for _ in [INF] * ((h + 1))]

for i in range(h + 1)[1:]:
    a[i] = list("#" + input())

memo[1][1] = 1
d = deque()
if a[2][1] == ".":
    d.append((2, 1))
if a[1][2] == ".":
    d.append((1, 2))


def dp(x, y):
    tmp = 0
    if a[x - 1][y] == ".":
        tmp = tmp + memo[x - 1][y]
    if a[x][y - 1] == ".":
        tmp = tmp + memo[x][y - 1]
    tmp = tmp % (10 ** 9 + 7)
    memo[x][y] = tmp
    return tmp


while len(d) > 0:
    x, y = d.popleft()
    if memo[x][y] == 0:
        dp(x, y)
        if x < h:
            if a[x + 1][y] == ".":
                d.append((x + 1, y))
        if y < w:
            if a[x][y + 1] == ".":
                d.append((x, y + 1))


ans = memo[h][w]

print("{}".format(ans))

Submission status: Accepted

Solution code:
def solve(n,m,ar):
    mod = int(1e9) + 7
    dp = [[0] * (m+2) for _ in range(n+2)]
    dp[1][1] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if ar[i][j] == "#": continue
            if i == 1 and j == 1: continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod

    print(dp[n][m])



if __name__ == '__main__':
    n,m = map(int,input().split())

    ar = [[-1] * (m+2) for i in range(n+2)]

    for i in range(1,n+1):
        temp = list(input())
        for j in range(1,m+1):
            ar[i][j] = temp[j-1]

    solve(n,m,ar)

Submission status: Accepted

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

grid[0][0]=1
for i in range(1,h):
	if(grid[i-1][0]==0):
		grid[i][0]=0
	elif(grid[i][0]=='#'):
		grid[i][0]=0
	else:
		grid[i][0]=grid[i-1][0]
for i in range(1,w):
	if(grid[0][i-1]==0):
		grid[0][i]=0
	elif(grid[0][i]=='#'):
		grid[0][i]=0
	else:
		grid[0][i]=grid[0][i-1]

for i in range(1,h):
	for j in range(1,w):
		if(grid[i][j]=='#'):
			grid[i][j]=0
		else:
			grid[i][j]=(grid[i][j-1]+grid[i-1][j])%mod
print(grid[h-1][w-1])
# import pprint
# grid.insert(0,grid)
# pprint.pprint(grid)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
l=[]
for i in range(n):
    a=input()
    p=[]
    for i in range(m):
        if a[i]=='#':
            p.append(-1)
        else:
            p.append(0)
    l.append(p)
dp=[[0 for j in range(m)]for i in range(n)]
for i in range(m):
    if l[0][i]!=-1:
        dp[0][i]=1
    else:
        break
for i in range(n):
    if l[i][0]!=-1:
        dp[i][0]=1
    else:
        break
mod=10**9+7
for i in range(1,n):
    
    for j in range(1,m):
        if l[i][j]!=-1:
            
            
                
                
                
            
            dp[i][j]+=((dp[i-1][j])%(mod) + (dp[i][j-1])%mod)%mod
        

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

prime = 10**9 + 7

def get(i, j, m, value):
    if i==h-1 and j==w-1:
        return 1
    if value[i][j]!=-1:
        return value[i][j]
    ans = 0
    if i < h-1 and m[i+1][j]=='.':
        value[i+1][j] = get(i+1, j, m, value)
        ans += value[i+1][j]
    if j < w-1 and m[i][j+1]=='.':
        value[i][j+1] = get(i, j+1, m, value)
        ans += value[i][j+1]
    return ans%prime

h, w = map(int,input().split())
m = []
for i in range(h):
    m.append(input())
value = [[-1 for i in range(w)] for j in range(h)]
ans = get(0, 0, m, value)
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7

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

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

dp[0][0]=1

judge1=1
judge2=1
for i in range(1,h):
  if maze[i][0]=='#':
    judge1=0
  dp[i][0]=judge1
    
for i in range(1,w):
  if maze[0][i]=='#':
    judge2=0
  dp[0][i]=judge2
    
for i in range(1,h):
  for j in range(1,w):
    if maze[i][j]=='#':
      dp[i][j]=0
    else:
      dp[i][j]=dp[i-1][j]+dp[i][j-1]
      dp[i][j]%=mod
      

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

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
mod=10**9+7
S=[]
for i in range(H):
  S.append(input())
  
total = [[0 for i in range(W)] for j in range(H)]
total[0][0] = 1

now = (0,0)
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':continue
    if i > 0 and S[i-1][j] != '#':
      total[i][j] += total[i-1][j]
    if j > 0 and S[i][j-1] != '#':
      total[i][j] += total[i][j-1]
    total[i][j] %= mod
        
print(total[-1][-1]%mod)