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:

R, C = map(int, input().split())
maze =["#"*(C+2)]+["#"+input()+"#" for i in range(R)]+["#"*(C+2)]
visited = [[0]*(C+2) for j in range(R+2)]
INF=10**9+7
for i in range(1,R+1):
    for j in range(1,C+1):
        if i==1 and j==1:visited[1][1]=1
        elif maze[i][j]==".":
            visited[i][j]=(visited[i-1][j]+visited[i][j-1])%INF
            if i==R and j==C:print(visited[i][j])

Submission status: Accepted

Solution code:
h,w =list(map(int,input().split()))
mod=10**9+7
a = [[i for i in input()] for j 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==0 and j==0: pass
		elif a[i][j]!="#":
			if i==0 : dp[i][j]=dp[i][j-1]
			elif j==0: dp[i][j]=dp[i-1][j]
			else:dp[i][j]=dp[i-1][j]+dp[i][j-1]
		else: dp[i][j]=0
		dp[i][j]=dp[i][j]%mod
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:


# target Expert  

# Author : raj1307 - Raj Singh
# Date   : 2.08.19

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii(): return int(input())
def si(): return input()
def mi(): return map(int,input().strip().split(" "))
def li(): return list(mi())

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import ceil,floor,log,sqrt,factorial,pow,pi
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *,threading
#from itertools import permutations

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[0] 
def sort2(l):return sorted(l, key=getKey)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():



    #for _ in range(ii()):

    n,m=mi()
    s=[]
    cache=d2(1005,1005,0)
    for i in range(n):
        s.append(list(si()))

    if s[0][0]=='#':
        print(0)
        exit()

    cache[1][1]=1






    for i in range(2,m+1):
        if s[0][i-1]=='.':
            cache[1][i]=cache[1][i-1]

    for i in range(2,n+1):
        if s[i-1][0]=='.':
            cache[i][1]=cache[i-1][1]


    for i in range(1,n+1):
        for j in range(1,m+1):

            if i!=1 and j!=1:
    
                if s[i-1][j-1]=='#':
                    cache[i][j]=0
                    continue
        
                if s[i-1][j-2]=='.':
                    cache[i][j]+=cache[i][j-1]

                if s[i-2][j-1]=='.':
                    cache[i][j]+=cache[i-1][j]


    print(cache[n][m]%mod)
    
    












    







# region fastio

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)

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

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Accepted

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

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

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

    for i in range(1,h):
        for j in range(1,w):
            if grid[i-1][j] == '.':
                dp[i][j] += dp[i-1][j]
            if grid[i][j-1] == '.':
                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())
s=[list(input()) for i in range(h)]
dp=[[0]*(w+2) for i in range(h+2)]
dp[0][1]=1

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
        else:
            pass
    
        
print(dp[h][w]%(10**9+7))

Submission status: Accepted

Solution code:
h, w = [ int(v) for v in input().split() ]

mod = 10**9+7
ans_list = [ 0 for i in range(w) ]
ans_list[0] = 1


line = input()
for i in range(1,w):
    if line[i] == ".":
        ans_list[i] = ans_list[i-1]
    else:
        ans_list[i] = 0


for j in range(1,h):
    new_ans_list = [ 0 for i in range(w) ]
    line = input()
    if line[0] == ".":
        new_ans_list[0] = ans_list[0] 
    else:
        new_ans_list[i] = 0

    for i in range(1,w):
        if line[i] == ".":
            new_ans_list[i] = (new_ans_list[i-1] + ans_list[i]) % mod
        else:
            new_ans_list[i] = 0

    ans_list = new_ans_list

print(ans_list[-1])

Submission status: Accepted

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(read_line(n=w))
    return a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    wall_symbol = '#'

    h = len(a)
    w = len(a[0])

    ways_count_to_get = [[0 for x in range(w)] for y in range(h)]
    ways_count_to_get[0][0] = 1

    for y in range(h):
        for x in range(w):
            if x == 0 and y == 0:
                continue
            if x == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y - 1][x]
                    continue
            if y == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y][x - 1]
                    continue
            if a[y][x] == wall_symbol:
                ways_count_to_get[y][x] = 0
            else:
                ways_count_to_get[y][x] = (ways_count_to_get[y - 1][x] + ways_count_to_get[y][x - 1]) % mode

    return ways_count_to_get[h - 1][w - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(read_line(n=w))
    return a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    wall_symbol = '#'

    h = len(a)
    w = len(a[0])

    ways_count_to_get = [[0 for x in range(w)] for y in range(h)]
    ways_count_to_get[0][0] = 1

    for y in range(h):
        for x in range(w):
            if x == 0 and y == 0:
                continue
            if x == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y - 1][x]
                    continue
            if y == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y][x - 1]
                    continue
            if a[y][x] == wall_symbol:
                ways_count_to_get[y][x] = 0
            else:
                ways_count_to_get[y][x] = (ways_count_to_get[y - 1][x] + ways_count_to_get[y][x - 1]) % mode

    return ways_count_to_get[h - 1][w - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(1000 * 1000)
    solve()

Submission status: Accepted

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

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

for i in range(H):
    maze[i] = list(str(input()))

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            dp[i+1][j+1] = 0
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]

print(dp[H][W] % 1000000007)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
Ms = [input().strip("\n") for _ in range(H)]

C = 10 ** 9 + 7
dp = [0] * (W + 1)
dp[0] = 1
for row in Ms:
    for i in range(len(row)):
        i1 = i + 1
        if row[i] == '#':
            dp[i1] = 0
        else:
            dp[i1] += dp[i]
            dp[i1] %= C
    dp[0] = 0
print(dp[W])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
dp=[[] for i in range(h)]
for i in range(h):
  for j in range(w):
    dp[i].append(0)
for i in range(h):
  b=input()
  a.append(b)
for i in range(h):
  if a[i][0]=="#":
    break
  dp[i][0]=1
for i in range(w):
  if a[0][i]=="#":
    break
  dp[0][i]=1
for i in range(1,h):
  for j in range(1,w):
    if a[i][j]=="#":
      continue
    else:
      dp[i][j]=dp[i-1][j]+dp[i][j-1]
ans=dp[h-1][w-1]
while(ans>1000000007):
  ans=ans%1000000007
print(ans)

Submission status: Accepted

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

a = [input().rstrip() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
for r in range(h):
    for c in range(w):
        if a[r][c] == '.':
            for rp, cp in ((r - 1, c), (r, c - 1)):
                if not (rp < 0 or cp < 0):
                    dp[r][c] += dp[rp][cp]
print(dp[-1][-1] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp7 #Grid 1

import sys
sys.setrecursionlimit(10000000)
def LI(): return list(map(int,sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
mod = 10**9+7

def h():
    h,w = LI()
    grid = [list(input()) for _ in range(h)]

    dp = [[0 for _ in range(w)] for _ in range(h)]
    dp[0][0] = 1
    for j in range(w-1):
        if grid[0][j+1] == '.':
            dp[0][j+1] += dp[0][j]
            dp[0][j+1] %= mod
    for i in range(h-1):
        if grid[i+1][0] == '.':
            dp[i+1][0] += dp[i][0]
            dp[i+1][0] %= mod
    #(i,j)が空マスであるとき(i-1,j)および(i,j-1)からの移動が考えられる
    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]
                dp[i][j] %= mod
    print(dp[-1][-1])
if __name__ == '__main__':
    h()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [sys.stdin.readline()[:-1] for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

H, W = LI()
a = LSR(H)

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

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

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])

Submission status: Accepted

Solution code:
import sys
H,W=list(map(int,input().strip().split(' ')))
grid=[]
for _ in range(H):
    grid+=[input()]
dp=[[0]*W for i in range(H)]
dp[0][0]=1
MOD=10**9+7
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        if grid[i][j]=="#":
            continue
        temp1=0
        temp2=0
        if i>0:
            temp1=dp[i-1][j]
        if j>0:
            temp2=dp[i][j-1]
        dp[i][j]=(temp1+temp2)%(MOD)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from __future__ import division, print_function
def main():
    n,m=map(int,input().split())
    l1=[]
    for i in range(n):
        l1.append(input())
    dp=[ [0]*m for _ in range(n)]
    dp[0][0]=1
    mod=10**9+7
    for i in range(n):
        for j in range(m):
            if l1[i][j]=='#':
                continue
            if i>0:
                if l1[i-1][j]=='.':
                    dp[i][j]=(dp[i][j]+dp[i-1][j])%mod
            if j>0:
                if l1[i][j-1]=='.':
                    dp[i][j]=(dp[i][j]+dp[i][j-1])%mod
    print(dp[n-1][m-1])


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

dp = [[None] * w for _ in range(h)]
# def dfs(hindex=h - 1, windex=w - 1):
#     if field[hindex][windex] == "#":
#         return 0
#     if hindex == windex == 0:
#         return 1
#
#     if dp[hindex][windex] is not None:
#         return dp[hindex][windex]
#     r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
#     dp[hindex][windex] = r
#     return r
#
# print(dfs() % (10**9 + 7))

for hindex in range(h):
    for windex in range(w):
        if hindex == windex == 0:
            dp[hindex][windex] = 1
        elif field[hindex][windex] == "#":
            dp[hindex][windex] = 0
        else:
            dp[hindex][windex] = (hindex and dp[hindex - 1][windex]) + (windex and dp[hindex][windex - 1])
print(dp[hindex][windex] % (10**9 + 7))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

dp = [[None] * w for _ in range(h)]
def dfs(hindex=h - 1, windex=w - 1):
    if field[hindex][windex] == "#":
        return 0
    if hindex == windex == 0:
        return 1

    if dp[hindex][windex] is not None:
        return dp[hindex][windex]
    r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
    dp[hindex][windex] = r
    return r

print(dfs() % (10**9 + 7))

Submission status: Accepted

Solution code:
# @author 

import sys

class HGrid1:
    def solve(self):
        MOD = 10 ** 9 + 7
        h, w = [int(_) for _ in input().split()]
        a = []
        for i in range(h):
            a.append(list(input()))

        dp = [[0] * (w + 1) for _ in range(h + 1)]
        for j in range(w):
            if a[0][j] == '#':
                break
            dp[0][j] = 1
        for i in range(h):
            if a[i][0] == '#':
                break
            dp[i][0] = 1
        for i in range(1, h):
            for j in range(1, w):
                if a[i][j] == '.':
                    if a[i - 1][j] == '.':
                        dp[i][j] += dp[i - 1][j]
                    if a[i][j - 1] == '.':
                        dp[i][j] += dp[i][j - 1]
                dp[i][j] %= MOD

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

solver = HGrid1()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

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

Submission status: Accepted

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

dp = []
for _ in range(H):
    row = [0] * W
    dp.append(row)
   
P = 1000000007
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
            
        if GRID[i][j] == '#':
            continue

        v = 0
        # up
        if i-1 >= 0:
            v = (v + dp[i-1][j]) % P
        # left
        if j-1 >= 0:
            v = (v + dp[i][j-1]) % P

        dp[i][j] = v

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

Submission status: Accepted

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

dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
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:
import sys
input = sys.stdin.readline

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

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
 
for y in range(H):
  for x in range(W):
    if y+1 < H and A[y+1][x] == '.':
      dp[y+1][x] += dp[y][x]
      dp[y+1][x] = dp[y+1][x] % MOD

    if x+1 < W and A[y][x+1] == '.':
      dp[y][x+1] += dp[y][x]
      dp[y][x+1] = dp[y][x+1] % MOD

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
mod = 10 ** 9 + 7
H, W = map(int, input().split())
field = []
dp = [[0] * W for _ in range(H)]

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

dp[0][0] = 1

for i in range(H):
	for j in range(W):
		if field[i][j] == '.':
			if i > 0:
				dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod
			if j > 0:
				dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod
				
print(dp[-1][-1])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
DVSR = 1000000007
def LI(): return [int(x) for x in input().split()]
H,W=LI()
MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and nx < W and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

H,W=LI()

MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and ny >= 0 and nx < W and nx >= 0 and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                # print('i:{},j:{},ny:{},nx:{},cost:{},pat:{}'.format(i,j,ny,nx,cost,pat))
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)
                # print('i:{},j:{},ny:{},nx:{},cost:{},pat:{}'.format(i,j,ny,nx,cost,_pat))
                # QU.append((ny,nx,cost,pat))
# for li in MEMO:
    # print(li)
print(MEMO[H-1][W-1][1])

Submission status: Accepted

Solution code:
r,c=map(int,input().split())
mod=10**9+7
dp=[[0]*(c+1) for i in range(r+1)]
a=[]
for i in range(r):
    a.append(input())
dp[0][1]=1
for i in range(1,r+1):
    for j in range(1,c+1):
        if(a[i-1][j-1]=='.'):
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
            #print((str(dp[i-1][j])+str(dp[i][j-1])),end=" ")
    #print()
#for i in dp:
#    print(i)
print(dp[r][c]%mod)