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:
# coding: utf-8

def dp(Hight, Width, lst_grid):
    dp_grid = [[0 for _ in range(Width)] for _ in range(Hight)]
    flag_w = False
    flag_h = False
    for h in range(Hight):
        for w in range(Width):
            if h==0:
                if lst_grid[h][w]=="#":
                    dp_grid[h][w:]==0
                    flag_w = True
                elif flag_w:
                    continue
                else:
                    dp_grid[h][w] = 1
            elif w==0:
                if lst_grid[h][w]=="#":
                    dp_grid[h:][w]==0
                    flag_h = True
                elif flag_h:
                    continue
                else:
                    dp_grid[h][w] = 1
            else:
                dp_grid[h][w] = dp_grid[h-1][w] + dp_grid[h][w-1]
            if lst_grid[h][w] == "#":
                dp_grid[h][w] = 0
    return dp_grid


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

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

Submission status: Accepted

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

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

for width in range(W):
    if map_info[0][width] == '.':
        path_pattern[0][width] = 1
    else:
        break
for height in range(H):
    if map_info[height][0] == '.':
        path_pattern[height][0] = 1
    else:
        break
for height in range(1, H):
    for width in range(1, W):
        if map_info[height][width] == '.':
            temp = (path_pattern[height-1][width]
                    + path_pattern[height][width-1]) \
                    % MOD
            path_pattern[height][width] = temp
        else:
            pass

print(path_pattern[-1][-1])

Submission status: Accepted

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

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

for h in range(H):
    for w in range(W):
        if Grid[h][w] == '.' and w + 1 < W and Grid[h][w + 1] == '.':
            field[h][w + 1] += field[h][w]
        if Grid[h][w] == '.' and h + 1 < H and Grid[h + 1][w] == '.':
            field[h + 1][w] += field[h][w]
print(field[H - 1][W - 1] % (10**9 + 7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan  6 21:36:22 2019

@author: Yamazaki Kenichi
"""

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

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


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

for j in range(1,H):
    if a[j][0] =='.':
        r[j][0] = r[j-1][0]
            
for j in range(1,H):
    for i in range(1,W):
        if a[j][i] == '.':
            r[j][i] = r[j-1][i]+r[j][i-1]

print(r[H-1][W-1]%1000000007)

Submission status: Accepted

Solution code:
mod = 1000000007
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
dp = [[0] * (w + 1) for i in range(h + 1)]
dp[1][1] = 1

for j in range(1, h + 1):
    for i in range(1, w + 1):
        if i == j == 1:
            continue

        if a[j - 1][i - 1] == '#':
            dp[j][i] = 0
        else:
            dp[j][i] = dp[j - 1][i] + dp[j][i - 1]
            dp[j][i] %= mod

print(dp[h][w])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
path = []
for i in range(H):
    path.append(input())
dp = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(1, H+1):
    if path[i-1][0] == "#":
        break
    else:
        dp[i][1] = 1
for i in range(1, W+1):
    if path[0][i-1] == "#":
        break
    else:
        dp[1][i] = 1
for i in range(1, H):
    for j in range(1, W):
        if path[i][j] == "#":
            dp[i+1][j+1] = 0
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % 1000000007
print(dp[H][W])

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
G = [raw_input().strip() for _ in xrange(H)]
dp = [[0 for i in xrange(W)] for _ in xrange(H)]
mod = 10**9 + 7

dp[0][0] = 1 if G[0][0] == '.' else 0

for i in xrange(H):
    for j in xrange(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]

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
fields = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
for i in range(h):
    if fields[i][0] == '#':
        break
    dp[i][0] = 1
for j in range(w):
    if fields[0][j] == '#':
        break
    dp[0][j] = 1
for i in range(1, h):
    for j in range(1, w):
        if fields[i][j] == '#':
            continue
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
print(dp[-1][-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
field = []
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = 1
for _ in range(h):
    field.append(input())
for column in range(1,w):
    dp[0][column] = int(field[0][column] != '#')*dp[0][column-1]
for row in range(1,h):
    dp[row][0] = int(field[row][0] != '#')*dp[row-1][0]
for row in range(1,h):
    for column in range(1,w):
        if field[row][column] == '#':
            dp[row][column] = 0
        else:
            dp[row][column] = (dp[row-1][column] + dp[row][column-1]) % 1000000007
print(dp[h-1][w-1])

Submission status: Accepted

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

# dp[h][w] := マス目(h, w)に辿り着く通り数
dp = [[0] * W for i in range(H)]
dp[0][0] = 1

for h in range(H):
    for w in range(W):
        if G[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())
P=10**9+7
a=[list(input()) for i in range(H)]
dp=[[0 for i in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if (i,j)==(0,0):
            dp[i][j]=1
        elif i==0:
            if dp[i][j-1]==1 and a[i][j]==".":
                dp[i][j]=1
            else:
                dp[i][j]=0
        elif j==0:
            if dp[i-1][j]==1 and a[i][j]==".":
                dp[i][j]=1
            else:
                dp[i][j]=0
        else:
            if a[i][j]=="#":
                dp[i][j]=0
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%P
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
src = [input() for i in range(H)]
MOD = 10**9+7

dp = [[0]*W for i in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if j+1 < W and src[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
        if i+1 < H and src[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
print(dp[-1][-1])

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        if MAP[i][j]=="#":
            continue
        if i!=0 and j!=0:
            DP[i][j]=(DP[i-1][j]+DP[i][j-1])%mod

        if i==0 and j!=0:
            DP[i][j]=DP[i][j-1]

        if i!=0 and j==0:
            DP[i][j]=DP[i-1][j]

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w = li()
MOD = 10**9+7

grid = []
grid.append("#"*(w+2))
for _ in range(h):
    grid.append("#" + ns() + "#")
grid.append("#"*(w+2))

ans = [[0]*(w+2) for _ in range(h+2)]
ans[1][1] = 1
for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == "." and (i,j) != (1,1):
            ans[i][j] = ans[i-1][j] + ans[i][j-1]
            ans[i][j] %= MOD
            
print(ans[h][w])

Submission status: Accepted

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

MOD = 10**9 + 7

dp = [[0]*(W+1) for i in range(H+1)]
dp[1][0] = 1
for i in range(H):
    s = S[i]
    for j in range(W):
        if s[j] == '#':
            continue
        dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % MOD
print(dp[H][W])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
grid = []
d = [(1, 0), (0, 1)]
for _ in range(H):
    grid.append(input())
dp = [[0 for _ in range(W)] for _ in range(H)]
mod = 1e9 + 7
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            continue
        if h > 0 and grid[h - 1][w] == '.':
            dp[h][w] += dp[h - 1][w]
        if w > 0 and grid[h][w - 1] == '.':
            dp[h][w] += dp[h][w - 1]
print(int(dp[H - 1][W - 1] % mod))

Submission status: Runtime Error

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

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: Runtime Error

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

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


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

Submission status: Runtime Error

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

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


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

Submission status: Runtime Error

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

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


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

Submission status: Runtime Error

Solution code:
def isInvalid(maze,i,j,dr,dc,visited):
    if i>dr or i<0 or j>dc or j<0:
        return True
    
    if visited[i][j]:
        return True
    
    if maze[i][j] == "#":
        return True
    
    return False

def grid(maze,i,j,dr,dc,visited):
    global count

    if i == dr and j == dc:
        count+=1
        
        return 
    
    if isInvalid(maze,i,j,dr,dc,visited):
        return
    visited[i][j] = True

    grid(maze,i,j+1,dr,dc,visited)
    grid(maze,i+1,j,dr,dc,visited)
    visited[i][j]= False

    



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

maze = []

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

count=0

visited = [[False]*w for _ in range(h)]
grid(maze,0,0,h-1,w-1,visited)
mod = 7+10**9
print(count%mod)

Submission status: Runtime Error

Solution code:
Q = 10**9 + 7
 
def f(h, w, field, ans):
    if ans[h][w] >= 0:
        return ans[h][w]
    else:
        ans[h][w] = 0
        fans = 0
        if 1 <= h + 1 <= H and 1 <= w <= W and field[h + 1][w] == ".":
            fans1 = f(h + 1, w, field, ans)
        else:
            fans1 = 0
        if 1 <= h <= H and 1 <= w + 1 <= W and field[h][w + 1] == ".":
            fans2 = f(h, w + 1, field, ans)
        else:
            fans2 = 0
        fans = (fans1 + fans2) % Q
        ans[h][w] = fans
        return fans
 
H, W = [int(x) for x in input().split()]
 
field = [' ' for _ in range(H + 1)]
 
for i in range(1, H + 1):
    field[i] += input()
 
ans = [[-1 for _ in range(W + 1)] for _ in range(H + 1)]
ans[H][W] = 1
 
A = f(1, 1, field, ans)
 
print(A)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
field = [input() for i in range(H)]
route_count_memory = [[-1] * W for i in range(H)]
route_count_memory[0][0] = 1

def get_route_count(i,j):
    result = 0
    if route_count_memory[i][j] != -1:
        return route_count_memory[i][j]
    if 0 <= i-1 < H and field[i-1][j] != '#':
        result += get_route_count(i-1, j)
    if 0 <= j-1 < W and field[i][j-1] != '#':
        result += get_route_count(i, j-1)
    route_count_memory[i][j] = result
    return result

print(get_route_count(H-1, W-1)%(10**9+7))

Submission status: Runtime Error

Solution code:
mod = 1000000007


def valid(i, j, n, m):
	if 0 <= i < n and 0 <= j < m:
		return True
	return False


def solve(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == n - 1 and j == m - 1:
		return 1
	sm = 0
	if valid(i + 1, j, n, m) and good[i + 1][j]:
		sm += solve(i + 1, j)
	if valid(i, j + 1, n, m) and good[i][j + 1]:
		sm += solve(i, j + 1)
	dp[i][j] = sm % mod
	return dp[i][j]


n, m = map(int, input().split())
good = [[] for i in range(n)]
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == '.':
			good[i].append(True)
		else:
			good[i].append(False)

dp = [[-1 for i in range(m)] for j in range(n)]
print(solve(0, 0))

Submission status: Runtime Error

Solution code:
mod = 1000000007


def valid(i, j, n, m):
	if 0 <= i < n and 0 <= j < m:
		return True
	return False


def solve(i, j):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == n - 1 and j == m - 1:
		return 1
	sm = 0
	if valid(i + 1, j, n, m) and ls[i + 1][j] != '#':
		sm += solve(i + 1, j)
	if valid(i, j + 1, n, m) and ls[i][j + 1] != '#':
		sm += solve(i, j + 1)
	dp[i][j] = sm % mod
	return dp[i][j]


n, m = map(int, input().split())
ls = []
for i in range(n):
	ls.append(input())
dp = [[-1 for i in range(m)] for j in range(n)]
print(solve(0, 0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod=10**9+7
m,n=map(int,input().split())
grid=[list(input()) for _ in range(n)]
cache={}
def dp(i,j):
  if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]=='#':
    return 0
  elif (i,j) in cache:
    return cache[(i,j)]
  elif i==m-1 and j==n-1:
    return 1
  cache[(i,j)]=dp(i+1,j)+dp(i,j+1)
  return cache[(i,j)]

print(dp(0,0)%mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod=10**9+7
m,n=map(int,input())
grid=[list(input()) for _ in range(n)]
cache={}
def dp(i,j):
  if i<0 or j<0 or i>=len(grid) or j>=grid[0] or grid[i][j]=='#':
    return 0
  elif (i,j) in cache:
    return cache[(i,j)]
  elif i==m-1 and j==n-1:
    return 1
  cache[(i,j)]=dp(i+1,j)+dp(i,j+1)
  return cache[(i,j)]

print(dp(0,0)%mod)

Submission status: Runtime Error

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
data = SLs(H)

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

for j in range(1,H):
  if data[j][0] != "#":
    dp[j][0] = dp[j-1][0]
for i in range(1,W):
  if data[0][i] != "#":
    dp[0][i] = dp[0][i-1]

for j in range(1,H):
  for i in range(1,W):
    if data[i][j] != "#":
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
      dp[i][j] %= MOD
      
print(dp[-1][-1])

Submission status: Runtime Error

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: Runtime Error

Solution code:
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):
  dp[0][i]=dp[0][i-1] if graph[0][i]=='.' else 0
for i in range(1,h):
  dp[i][0]=dp[i-1][0] if graph[0][i]=='.' else 0
for i in range(1,h):
  for j in range(1,w):
    #print(i-1,j-1)
    if(graph[i-1][j-1]=='#'):
      dp[i][j]=0
    else:
      dp[i][j]=(dp[i-1][j]+dp[i][j-1])%(1e9 + 7)

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

Submission status: Runtime Error

Solution code:
v=pow(10,9)+7
arr=[]
inp = list(map(int,input().split()))
row=inp[0]
col=in[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:
      arr[i][j]=(arr[i-1][j]+arr[i][j-1])%v
print (arr[-1][-1])

Submission status: Runtime Error

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[gy][gx]%R)

Submission status: Runtime Error

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(m):
    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: Runtime Error

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

dp = [[-1] * W for _ in range(H)]
dp[H-1][W-1] = 1
que = deque()
que.append((H-2, W-1))
que.append((H-1, W-2))
visited = set([(H-1, W-1)])
while len(que) > 0:
    h, w = que.popleft()
    visited.add((h, w))
    steps = 0
    if h < H-1 and m[h+1][w] == "." and ((h+1, w) in visited):
        steps += dp[h+1][w]
    if w < W-1 and m[h][w+1] == "." and ((h, w+1) in visited):
        steps += dp[h][w+1]
    steps %= mod
    dp[h][w] = steps

    if not ((h-1, w) in visited) and h-1 >= 0 and m[h-1][w] == ".":
        que.append((h-1, w))
    if not ((h, w-1) in visited) and w-1 >= 0 and m[h][w-1] == ".":
        que.append((h, w-1))

print(dp[0][0])

Submission status: Runtime Error

Solution code:


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

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








flag= False
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: Runtime Error

Solution code:

import copy
H, W = list(map(int , input().split(' ')))

arr =  []
h_ar = []
for _ in range(W):
    h_ar.append(0)
dp =[]
for _ in range(H):
    dp.append(copy.deepcopy(h_ar))


for _ in range(H):
    w  =  list(map(str , input().split(' ')))
    arr.append(w)


flag= False
for h in range(H-1,-1,-1):
    if arr[h][W-1]=='#':

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



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]=-1
        elif dp[row][col-1] ==-1 or dp[row-1][col]==-1:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
        elif dp[row][col-1] > -1 and dp[row-1][col]>-1:
             dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]

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

Submission status: Runtime Error

Solution code:

import copy
H, W = list(map(int , input().split(' ')))

arr =  []
h_ar = []
for _ in range(W):
    h_ar.append(0)
dp =[]
for _ in range(H):
    dp.append(copy.deepcopy(h_ar))


for _ in range(H):
    w  =  list(map(str , input().split(' ')))
    arr.append(w)
print(arr)


flag= False
for h in range(H-1,-1,-1):
    if arr[h][W-1]=='#':

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



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]=-1
        elif dp[row][col-1] ==-1 or dp[row-1][col]==-1:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
        elif dp[row][col-1] > -1 and dp[row-1][col]>-1:
             dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]

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

Submission status: Runtime Error

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

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

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


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

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



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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

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


dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[1][i] == "#":
        addi = 0
    dp[1][i] += addi
addi = 1
for i in range(1,w+1):
    if a[i][1] == "#":
        addi = 0
    dp[i][1] += addi
"""
#print(dp)
def rec(stage,y,x,dp_c):
    #print(y,x)
    if stage[y][x] == "#":
        return 0
    else:
        dp_c[y][x] = max(dp_c[y][x],rec(stage,y-1,x,dp_c) + rec(stage,y,x-1,dp_c))%(10**9+7)
        return dp_c[y][x]
rec(a,h,w,dp)
"""
for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "#":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])
#for i in range(h+2):
#    print(dp[i])