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:
n = input().split()
r = int(n[0])
c = int(n[1])

a = []
MOD = 10**9+7

for i in range(r):
    x = input()
    y = []
    for char in x:
        if char == '.':
            y.append(1)
        else:
            y.append(0)
    a.append(y)

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

    dp[0][0] = a[0][0]

    for i in range(1,r):
        dp[i][0] = dp[i-1][0] * a[i-1][0]

    for j in range(1,c):
        dp[0][j] = dp[0][j-1] * a[0][j-1]

    for i in range(1,r):
        for j in range(1,c):
            dp[i][j] = dp[i-1][j] * a[i-1][j] + dp[i][j-1] * a[i][j-1]

print((dp[r-1][c-1] * a[r-1][c-1])%MOD)

Submission status: Accepted

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

grid = [None] * H

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

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

dp[1][1] = 1
M = 10 ** 9 + 7

for L in range(1,H + 1):
    for C in range(1,W + 1):
        if L == 1 and C == 1:
            continue
        else:
            if grid[L-1][C-1] == ".":
                dp[L][C] = dp[L][C-1] + dp[L-1][C]
                dp[L][C] %= M

print(dp[H][W])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
m = [['#'] * (w+2) for i in range(h+2)]
for j in range(h):
    m[j+1][1:w+1] = list(input()) #適宜変える

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

dp[1][1] = 1

for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i-1][j] == '.':
            dp[i][j] += dp[i-1][j]
        if m[i][j-1] == '.':
            dp[i][j] += dp[i][j-1]

print(dp[h][w] % 1000000007)

Submission status: Accepted

Solution code:
def main():
    m = 1000000007

    h, w = map(lambda x: int(x), input().split())

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

    count = []
    for row in range(h):
        count.append([0] * w)

    for row in range(h):
        if grid[row][0] == "#":
            break
        count[row][0] = 1

    for column in range(w):
        if grid[0][column] == "#":
            break
        count[0][column] = 1

    for row in range(1, h):
        for column in range(1, w):
            if grid[row][column] == ".":
                count[row][column] = (
                    (count[row - 1][column] % m) +
                    (count[row][column - 1] % m)
                ) % m

    print(count[-1][-1])

main()

Submission status: Accepted

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

grid = []

for i in range(h):
    row = list(input()) 

    for i in range(len(row)):
        if row[i] == '.':
            row[i] = 0
    
    grid.append(row)

num = 1000000007

for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == '#':
            continue
        if i == 0 and j == 0:
            grid[i][j] = 1
        elif i == 0:
            if grid[i][j-1] != '#':
                grid[i][j] = grid[i][j-1] % num
        elif j == 0:
            if grid[i-1][j] != '#':
                grid[i][j] = grid[i-1][j] % num
        else:
            if grid[i][j-1] == '#' and grid[i-1][j] == '#':
                grid[i][j] = 0
            elif grid[i][j-1] == '#':
                grid[i][j] = grid[i-1][j] % num
            elif grid[i-1][j] == '#':
                grid[i][j] = grid[i][j-1] % num
            else:
                grid[i][j] = (grid[i-1][j] + grid[i][j-1]) % num

print(grid[-1][-1])

Submission status: Accepted

Solution code:
x, y = map(int, input().split())
grid = []
visit = []
mod = 1000000007
for _ in range(x):
    grid.append([i for i in input()])
    visit.append([0 for i in range(y)])
grid[x-1][y-1] = 'X'
visit[x-1][y-1] = 1
for i in range(x-1, -1, -1):
    for j in range(y-1, -1, -1):
        if grid[i][j] == '.':
            if i < x-1 and j < y-1:
                visit[i][j] = (visit[i][j+1] + visit[i+1][j])%mod
            elif i < x-1 and j == y-1:
                visit[i][j] = visit[i+1][j]
            else:
                visit[i][j] = visit[i][j+1]
print(visit[0][0])

Submission status: Accepted

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

dp = [[0] * (w + 1) for _ in range(h + 1)]
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        if hi == 1 and wi == 1:
            dp[hi][wi] = 1
            continue
        if a[hi][wi] == ".":
            dp[hi][wi] = dp[hi-1][wi] + dp[hi][wi-1]
            dp[hi][wi] %= mod

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1
M = 10**9+7
for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            continue
        if a[i-1][j-1]==".":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= M
print(dp[h][w])

Submission status: Accepted

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

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if a[i][j] == '#': 
            continue
        if i + 1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= 1e9 + 7
        if j + 1 < W and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= 1e9 + 7
        
print(int(dp[-1][-1]))

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
H, W = LI()
A = [input() for _ in range(H)]

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if A[i][0] == "#":
            break
        dp[i][0] = 1
    for j in range(W):
        if A[0][j] == "#":
            break
        dp[0][j] = 1
    for i in range(1, H):
        for j in range(1, W):
            if A[i - 1][j] == ".":
                dp[i][j] = dp[i - 1][j]
            if A[i][j - 1] == ".":
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD
    ans = dp[-1][-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 1000000007
H, W = (int(x) for x in input().split())
grid = []
for row in range(H):
  grid.append(input())
# Number of paths to get to end grid[i][j]
dp = [[0 for i in range(W)] for i in range(H)]
# dp[H-1][W-1] == '#' ? 1 : return 0
if grid[H-1][W-1] == '#':
  print(0)
else:
  dp[H-1][W-1] = 1

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

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

Submission status: Accepted

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

m = 1000000007

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for w in range(1, W):
    if a[0][w] != '#':
        dp[0][w] = dp[0][w - 1]

for h in range(1, H):
    if a[h][0] != '#':
        dp[h][0] = dp[h - 1][0]
    for w in range(1, W):
        if a[h][w] != '#':
            dp[h][w] = (dp[h][w - 1] + dp[h - 1][w]) % m

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

Submission status: Accepted

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

m = 1000000007

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for h in range(H - 1):
    for w in range(W - 1):
        if a[h][w] == '#':
            continue
        if a[h][w + 1] != '#':
            dp[h][w + 1] = (dp[h][w + 1] + dp[h][w]) % m
        if a[h + 1][w] != '#':
            dp[h + 1][w] = (dp[h + 1][w] + dp[h][w]) % m
    if a[h][W - 1] == '#':
        continue
    if a[h + 1][W - 1] != '#':
        dp[h + 1][W - 1] = (dp[h + 1][W - 1] + dp[h][W - 1]) % m
for w in range(W - 1):
    if a[H - 1][w] == '#':
        continue
    if a[H - 1][w + 1] != '#':
        dp[H - 1][w + 1] = (dp[H - 1][w + 1] + dp[H - 1][w]) % m

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=1000000007
h,w=map(int,input().split())
grid=[]
for _ in range(h):
    s=list(input())
    grid.append(s)

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 grid[i][j]=='#':
            continue
        if i>0:
            dp[i][j]+=dp[i-1][j]%mod
        
        if j>0:
            dp[i][j]+=dp[i][j-1]%mod
        
print(dp[h-1][w-1]%mod)

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	m = [0,-1]
	for test in range(tests):
		[n,m] = inlt()
		grid = []
		for i in range(n):
			grid.append(insr())
		dp = [[0 for j in range(m)] for i in range(n)]
		dp[-1][-1] = 1
		move = {}
		move[(n-1,m-1)] =1
		while(move != {}):
			n_move = {}
			# print(dp)
			for i in move:
				
				if i[0]-1 >=0 and grid[i[0]-1][i[1]] == ".":
					dp[i[0]-1][i[1]] = (dp[i[0]-1][i[1]]+ dp[i[0]][i[1]])%mod
					n_move[ (i[0]-1,i[1]) ] =1
				if i[1]-1 >=0 and grid[i[0]][i[1]-1]  == "." :
					dp[i[0]][i[1]-1] = (dp[i[0]][i[1]-1]+ dp[i[0]][i[1]])%mod
					n_move[ (i[0],i[1]-1) ] =1
			move = n_move
		print(dp[0][0])


if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
arr = [list(map(str, input().rstrip())) for _ in range(h)]
MOD = 10**9 + 7

# dpテーブル
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 arr[i - 1][j - 1] == "#":
            continue
        else:
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1]

print(dp[h][w] % MOD)

Submission status: Accepted

Solution code:
mod=10**9+7

H,W=map(int,input().split())
a=[list(input()) for _ in range(H)]
a[0][0]=1
for h in range(H):
    for w in range(W):
        if h==0:
            if w==0:
                continue
            if a[h][w]==".":
                a[h][w]=a[h][w-1]
            else:
                a[h][w]=0
        else:
            if a[h][w]=="#":
                a[h][w]=0
            elif w==0:
                a[h][w]=a[h-1][w]
            else:
                a[h][w]=(a[h-1][w]+a[h][w-1])%mod
print(a[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=1e9+7
def addself(a):
    if(a<mod):
        return a
    else:
        return (a+mod)%mod
    
n,m=map(int,input().split())
x = []
dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1][1] = 1
for i in range(n):
    l = list(input())
    x.append(l)
for i in range(1,n+1):
    for j in range(1,m+1):
        if i ==1 and j==1:
            continue
        if x[i-1][j-1]=='#':
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j]+dp[i][j-1]

        dp[i][j]=addself(dp[i][j])
            
print(int(dp[-1][-1]))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def solve(h, w, a):
    dp = [[0]*(w+1) for y in range(h+1)]
    dp[0][0] = 1
    for y in range(h):
        for x in range(w):
            if a[y][x] == ".":
                dp[y+1][x] = (dp[y+1][x] + dp[y][x]) % MOD
                dp[y][x+1] = (dp[y][x+1] + dp[y][x]) % MOD
    return dp[h-1][w-1]

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
wall=[list(input()) for i 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==0 and j==0:
      continue
    tmp=0
    if i > 0 and wall[i-1][j]=='.':
      tmp+=dp[i-1][j]
    if j > 0 and wall[i][j-1]=='.':
      tmp+=dp[i][j-1]
    dp[i][j]+=tmp
print(dp[h-1][w-1] % 1000000007)

Submission status: Accepted

Solution code:
md = 1000000007
n,m = map(int,input().split())

grid=[]
for i in range(n):
    grid.append(list(input()))

dp=[]
for i in range(n):
    dp.append([0]*m)
dp[0][0]=1
for i in range(1,n):
    if(grid[i][0]!="#"):
        dp[i][0]=dp[i-1][0]
    else:
        dp[i][0]=0

for j in range(1,m):
    if(grid[0][j]!="#"):
        dp[0][j]=dp[0][j-1]
    else:
        dp[0][j]=0

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

Submission status: Accepted

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

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 0
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}
mod = 10**9+7

from collections import deque

def bfs(init):
    next_q = deque([])
    for hi, hw in init:
        next_q.append([hi,hw])
        Dist[hi][hw] = 1

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.':
                if Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                Dist[hs][ws] += Dist[h][w]
                Dist[hs][ws] %= mod
    return Dist

def main():
    ret = bfs([[sth, stw]])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(100000)
 
H, W = map(int, input().split())

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

memo = [[-1 for i in range(W)] for j in range(H)]

def move(x, y):
    if x >= W or y>=  H:
        return 0
    if x == W-1 and y == H-1:
        return 1
    if stage[y][x] == "#":
        return 0
    if memo[y][x] != -1:
        return memo[y][x]
    p = move(x+1, y)+move(x,y+1)
    memo[y][x] = p
    return p

print(move(0,0)%(10**9+7))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = list(input() for i in range(h))

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

mod = 10 ** 9 + 7

for i in range(h):
  for j in range(w):
    if(i + 1 < h and a[i + 1][j] == '.'):
      dp[i + 1][j] += dp[i][j]
      if(dp[i + 1][j] >= mod):
        dp[i + 1][j] -= mod
    if(j + 1 < w and a[i][j + 1] == '.'):
      dp[i][j + 1] += dp[i][j]
      if(dp[i][j + 1] >= mod):
        dp[i][j + 1] -= mod

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

Submission status: Accepted

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

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

for h in range(H):
    for w in range(W):
        if h+1 < H and m[h+1][w] == ".":
            dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= mod
        if w+1 < W and m[h][w+1] == ".":
            dp[h][w+1] += dp[h][w]
            dp[h][w+1] %= mod

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mat=[]
for i in range(h):
    a=[i for i in list(input())]
    mat.append(a)
for i in range(w):
    if mat[0][i]=='.':
        mat[0][i]=1
    else:
        for j in range(i,w):
            mat[0][j]=0
        break
for i in range(1,h):
    for j in range(w):
        if mat[i][j]=='.':
            mat[i][j]=0
            mat[i][j]=(mat[i][j]+mat[i-1][j])%1000000007
            if j-1>=0:
                mat[i][j]=(mat[i][j]+mat[i][j-1])%1000000007
        else:
            mat[i][j]=0

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

Submission status: Accepted

Solution code:
import sys
import math
from  collections import defaultdict


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

mod = 1000000007

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


	dp = [[0 for j in range(w)] for i in range(h)]
	dp[0][0] = 1
	for j in range(1, w):
		if grid[0][j] == '.':
			dp[0][j] += dp[0][j - 1]

	for i in range(1, h):
		if grid[i][0] == '.':
			dp[i][0] += dp[i - 1][0]

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

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




if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Accepted

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

Submission status: Accepted

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

dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        if i+1<h and a[i+1][j]=='.':
            dp[i+1][j]+=dp[i][j]%(10**9+7)
        if j+1<w and a[i][j+1]=='.':
            dp[i][j+1]+=dp[i][j]%(10**9+7)
print(dp[h-1][w-1]%(10**9+7))

Submission status: Accepted

Solution code:


H, W = map(int, input().split())
arr = ['']*H
for i in range(H):
    arr[i] = input()
 
#print(arr)
dp = [[0]*W for _ in range(H)]

# arr =[
# ['.','.'],
# ['#','.'],
# ['.','.'],
# ['.','#'],
# ['.','.']
# ]








flag= False
#print(arr)
for h in range(H-1,-1,-1):
    #print(h,W-1)

    if arr[h][W-1]=='#':
        dp[h][W-1]=0
        flag =  True
    if flag:
        dp[h][W-1]=0
    else:
        dp[h][W-1]=1
#print(dp)
    
flag = False
for w in range(W-1,-1,-1):
    #print(h,W-1)
    if arr[H-1][w]=='#':
        dp[H-1][w]=0
        flag =  True
    if flag:
        dp[H-1][w]=0
    else:
        dp[H-1][w]=1


#print(dp)

MOD = 10**9+7

dp[H-1][W-1]=0

for row in range(H-1,0,-1):
    for col in range(W-1,0,-1):
        if arr[row-1][col-1]=='#':
            dp[row-1][col-1]=0
        elif dp[row][col-1] ==0 or dp[row-1][col]==0:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
            dp[row-1][col-1]%=MOD

        elif dp[row][col-1] > 0 and dp[row-1][col]>0:
            dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]
            dp[row-1][col-1]%=MOD
        elif  dp[row][col-1] == 0 and dp[row-1][col] == 0:
            dp[row-1][col-1]==0


print(dp[0][0])

Submission status: Accepted

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

grid=[]
for i in range(n):
  x=list(input())
  grid.append(x)
  

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

Submission status: Accepted

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

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


dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = 1
MOD = 10**9 + 7

for i in range(h):
    for j in range(w):
        if grid[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:
MOD = int(1e9+7)

h, w = map(int, input().split())
dp = [[0]*w for i in range(h)]
dp[-1][-1] = 1

g = []

for i in range(h):
    g.append([i for i in input()])

for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
        if i == h-1 or j == w-1:
            if g[i][j] == "#":
                dp[i][j] = 0
            elif i == h-1 and j != w-1:
                dp[i][j] = dp[i][j+1]
            elif j == w-1 and i != h-1:
                dp[i][j] = dp[i+1][j]
        else:
            if g[i][j] == "#":
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
                
        dp[i][j] %= MOD
                
                
print(dp[0][0])

Submission status: Accepted

Solution code:
def solve(result,rows,cols):
    MOD=10**9+7

    t={"#":1,".":0}
    dp=[[1]*cols for i in range(rows)]
    dp[0][0]=1
    for j in range(1,cols):
        dp[0][j]=dp[0][j-1]*(1-t[result[0][j]])
    for i in range(1,rows):
        dp[i][0]=dp[i-1][0]*(1-t[result[i][0]])
        
    for i in range(1,rows):
        for j in range(1,cols):
            if result[i][j]=="#":
                dp[i][j]=0
            else:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            
            
    return dp[-1][-1]%MOD

        
    


value=[int(i) for i in input().split()]
rows,cols=value[0],value[1]
result=[]
for i in range(rows):
    t=input()
    result.append(t)
#result=[[str(i) for i in input().split()]for j in range(rows)]
print(solve(result,rows,cols))

Submission status: Accepted

Solution code:
MOD = 10**9+7

H, W = map(int, input().split())
a = ['']*H
for i in range(H):
    a[i] = input()

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i+1 < H and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j+1 < W and 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:
def main():
    H, W = list(map(int, input().split()))
    dp = [['0'] * (W + 2)] + [['0', ] + ['0' if a == '#' else a for a in list(input())] + ['0', ] for _ in range(H)] + [['0'] * (W + 2)]
    mod = 1000000007
    dp[1][1] = '1'
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if dp[h][w] == '.':
                dp[h][w] = str((int(dp[h - 1][w]) + int(dp[h][w - 1])) % mod)
    print(dp[H][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(H,0,-1):
    for j in range(W,0,-1):
        if field[i][j] == '#':
            continue
        else:
            dp[i][j] += dp[i][j+1] + dp[i+1][j]
        dp[i][j] %= MOD

print(dp[1][1])

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer

import numpy as np
MOD = 10 ** 9 + 7

H,W = map(int,buf.readline().split())

grid = np.frombuffer(buf.read(),dtype='S1').reshape(H,-1)[:,:W]

#print(grid)

MOD = 10 ** 9 + 7
dp = np.zeros(W, dtype = np.int64)
dp[0] = 1

for row in grid:
  #print(row == b"#")
  wall = (row == b'#')
  # 上から落としてくる
  dp[wall] = 0
  # 左から右に
  np.cumsum(dp, out = dp)
  # 壁の補正
  sub = np.maximum.accumulate(dp * wall)
  dp -= sub
  dp %= MOD

answer = dp[-1]
print(answer)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
mod=10**9+7
grid=[]
for i in range(H):
    s=str(input())
    grid.append(s)
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 (grid[i+1][j]=="."):
            dp[i+1][j]+=dp[i][j]
        if (j+1 < W) and (grid[i][j+1]=="."):
            dp[i][j+1]+=dp[i][j]
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    dp = [[0 for _ in range(W)] for _ in range(H)]
    for w in range(W):
        if A[0][w] == '#':
            break
        dp[0][w] = 1
    for h in range(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])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
z=(10**9)+7
for _ in range(n):
    s=input()
    b=[str(x) for x in s]
    a.append(b)
dp=[[0 for i in range(m)]for j in range(n)]
dp[0][0]=1
for i in range(1,m):
    if dp[0][i-1]==1 and a[0][i]!='#':
        dp[0][i]=1
for i in range(1,n):
    if dp[i-1][0]==1 and a[i][0]!='#':
        dp[i][0]=1
for i in range(1,n):
    for j in range(1,m):
        if a[i][j]!='#':
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(dp[n-1][m-1]%z)

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))

def grid3():
	MOD = pow(10,9) + 7
	H, W = read()
	 
	grid = [[0]*W for h in range(H)]
	grid[0][0] = 1
	 
	for h in range(H) :  
	  row = input()
	 
	  for w in range(W) :
	    if row[w] == '#' : continue
	    if h > 0 : grid[h][w] += grid[h-1][w]
	    if w > 0 : grid[h][w] += grid[h][w-1]
	    grid[h][w] %= MOD
	print(grid[-1][-1]% MOD)


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