Problem:


Score : 100 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns.
Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.

For each i and j (1 \leq i \leq H, 1 \leq j \leq W), Square (i, j) is described by a character a_{i, j}.
If a_{i, j} is ., Square (i, j) is an empty square; if a_{i, j} is #, Square (i, j) is a wall square.
It is guaranteed that Squares (1, 1) and (H, W) are empty squares.

Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square (1, 1) to (H, W).
As the answer can be extremely large, find the count modulo 10^9 + 7.

Constraints

H and W are integers.

2 \leq H, W \leq 1000

a_{i, j} is . or #.

Squares (1, 1) and (H, W) are empty squares.

Input

Input is given from Standard Input in the following format:

H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}

Output

Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Sample Input 1

3 4
...#
.#..
....

Sample Output 1

3

There are three paths as follows:

Sample Input 2

5 2
..
#.
..
.#
..

Sample Output 2

0

There may be no paths.

Sample Input 3

5 5
..#..
.....
#...#
.....
..#..

Sample Output 3

24

Sample Input 4

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

Sample Output 4

345263555

Be sure to print the count modulo 10^9 + 7.



Sample input:
3 4
...#
.#..
....


Sample output:
3

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class ModInt(int):
    
    MOD = 7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)
    
    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)
    
    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)
    
    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)
    
    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()
    
    def __truediv__(self, other):
        return ModInt(super().__mul__(pow(other, ModInt.MOD-2, ModInt.MOD)))
    
    def __floordiv__(self, other):
        return self.__truediv__(other)
    
    def __rtruediv__(self, other):
        return ModInt(self.__pow__(ModInt.MOD-2).__mul__(other))
    
    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)


def read():
    ModInt.MOD = 10**9+7
    H, W = map(int, input().strip().split())
    M = []
    for i in range(H):
        M.append(input().strip())
    return H, W, M


def solve(H, W, M):
    dp = [ModInt(0) for i in range(W+1)]
    dp[1] = 1
    for i in range(1, H+1):
        for j in range(1, W+1):
            dp[j] = (dp[j] + dp[j-1]) if M[i-1][j-1]=='.' else 0
    return dp[W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
field = ["#"*(W+2)]
field += ["#"+input()+"#" for _ in range(H)]
field += ["#"*(W+2)]
dp = [[0]*(W+2) for _ in range(H+2)]
dp[1][1] = 1

#i,jへの最短経路の個数
for i in range(H+2):
  for j in range(W+2):
    if field[i][j] == ".":
      dp[i][j] = max(dp[i-1][j] + dp[i][j-1],dp[i][j])
    
print(dp[H][W]%1000000007)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [""]*h
mod = 10**9+7
for i in range(h):
  si = str(input())
  s[i] = si
x = [1]*w
for i in range(w):
  if s[0][i] == "#":
    for j in range(i,w):
      x[j] = 0
    break
for i in range(1,h):
  newx = [0]*w
  if s[i][0] == ".":
    newx[0] = x[0]
  for j in range(1,w):
    if s[i][j] == ".":
      newx[j] = (newx[j-1]+x[j])%mod
    else:
      newx[j] = 0
  x = newx
print(x[w-1])

Submission status: Accepted

Solution code:
#input
H, W = map(int, input().split())
a = ["" * W for _ in range(H)]
for i in range(H):
    a[i] = list(map(str, input().split()))

#output
mod = 10**9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
mod = 10**9 + 7
h, w = [int(x) for x in input().split()]
g = [list(input().rstrip()) for _ in range(h)]

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

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if g[i][j] == "#":
            continue
        xy = [(i - 1, j), (i, j - 1)]
        for k in xy:
            x, y = k
            if 0 <= x < h and 0 <= y < w:
                dp[i][j] += dp[x][y]
                dp[i][j] %= mod

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

Submission status: Accepted

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

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

for i in range(1,H+1):
    for j in range(1,W+1):
        if G[i-1][j-1]=='#':
            DP[i][j]=0
        else:
            DP[i][j]+=DP[i-1][j]+DP[i][j-1]
            DP[i][j]=DP[i][j]%P


print(DP[H][W])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

MODULO = pow(10, 9) + 7


def solve_matrix(values, h, w):
    dp = [[0] * (1 + w) for _ in range(1 + h)]
    dp[1][1] = 1
    for i in range(h):
        for j in range(w):
            if i + j != 0 and values[i][j] == ".":
                LOG.debug((i, j, values[i][j]))
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MODULO
    LOG.debug("\n".join(map(str, dp)))
    return dp[h][w]


def solve(values, h, w):
    dp = [0] * w
    dp[0] = 1
    for i in range(h):
        LOG.debug((dp))
        prev = dp.copy()
        dp = [0] * w
        for j in range(w):
            LOG.debug((i, j, values[i][j]))
            if i + j == 0:
                dp[j] = 1
                continue
            if values[i][j] == "#":
                LOG.debug(("skipped"))
                continue
            if j != 0:
                dp[j] = (dp[j] + dp[j - 1]) % MODULO
            dp[j] = (dp[j] + prev[j]) % MODULO
    LOG.debug((dp))
    return dp[w - 1]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    H, W = map(int, input().split())
    values = []
    for _ in range(H):
        values.append(input())
    # result = solve_matrix(values, H, W)
    result = solve(values, H, W)
    print(result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

MODULO = pow(10, 9) + 7


def solve(values, h, w):
    dp = [[0] * (1 + w) for _ in range(1 + h)]
    dp[1][1] = 1
    for i in range(h):
        for j in range(w):
            if i + j != 0 and values[i][j] == ".":
                LOG.debug((i, j, values[i][j]))
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MODULO
    LOG.debug("\n".join(map(str, dp)))
    return dp[h][w]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    H, W = map(int, input().split())
    values = []
    for _ in range(H):
        values.append(input())
    result = solve(values, H, W)
    print(result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
def solve():
    MOD = 10 ** 9 + 7
    H, W = map(int,input().split())
    a = [list(input()) for _ in range(H)]
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1

    for h in range(H):
        for w in range(W):
            if w-1 >= 0 and a[h][w-1] == '.':
                dp[h][w] += dp[h][w-1] % MOD
            if h-1 >= 0 and a[h-1][w] == '.':
                dp[h][w] += dp[h-1][w] % MOD

    print(dp[-1][-1] % MOD)
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def list2d(a, b, c): return [[c] * b for i in range(a)]
mod =10**9+7
H, W = map(int, input().split())

grid = []

for _ in range(H):
    grid.append(list(input()))

dp = list2d(H, W, 0)
for i in range(H-1, -1, -1):
    if(grid[i][W-1] == '#'):
        break
    dp[i][W-1] = 1

for j in range(W-1, -1, -1):
    if(grid[H-1][j]=='#'):
        break
    dp[H-1][j] = 1

for row in range(H-2, -1, -1):
    for col in range(W-2, -1, -1):
        if(grid[row][col] == '.'):
            dp[row][col] = (dp[row][col+1] + dp[row+1][col])%mod
        else:
            dp[row][col] = 0
print(dp[0][0]%mod)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

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

#dp[i][j]は(i,j)までの経路の数
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            dp[i][j] = 0
            continue

        if i > 0 and j > 0:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        elif i > 0:
            dp[i][j] = dp[i - 1][j]
        elif j > 0:
            dp[i][j] = dp[i][j - 1]
        else:
            dp[i][j] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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


submit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    h,w = map(int, input().split())
    maze = [input() for _ in range(h)]
    dp = [[1] * w for _ in range(h)]
    for i,s in enumerate(maze):
        for j,t in enumerate(s):
            if t == '#':
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] == 1
            elif 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]
    ans = dp[h-1][w-1] % (10**9+7)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    H, W = map(int, input().split())
    maze = [list(input().rstrip()) for _ in range(H)]
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if maze[i][j] == "#":
                continue
            if i + 1 < H: dp[i+1][j] += dp[i][j]
            if j + 1 < W: dp[i][j+1] += dp[i][j]
    print(dp[H-1][W-1] % (10**9+7))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
inf = 10**9+7
maze = [list(input()) for i in range(H)]
dp = [[0 for i in range(W+1)] for j in range(H+1)]

#dp[i+1][j+1]:maze[i][j]に至るまでの方法の数
#dp[0][0] = 1
#dp[i][j] = dp[i][j-1] + dp[i-1][j]

dp[1][1] = 1
maze[0][0] = '#' #こうすると都合がいい
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

def input():
    return sys.stdin.readline()[:-1]
  
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

dp = np.zeros(W+1, dtype=int)
dp[1] = 1

for i in range(1,H+1):
    prev = dp.copy()
    for j in range(1,W+1):
        if eq[i-1][j-1]:
            dp[j] = prev[j] + dp[j-1]
        else:
            dp[j] = 0
    dp %= mod

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

dp = np.zeros(W+1, dtype=int)
dp[1] = 1

for i in range(1,H+1):
    prev = dp.copy()
    for j in range(1,W+1):
        if eq[i-1][j-1]:
            dp[j] = prev[j] + dp[j-1]
        else:
            dp[j] = 0
    dp %= mod

print(dp[-1])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
DP_1 = ["."*(W+1)]
for _ in range(H):
    A = "."+input()
    DP_1.append(A)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        if DP_1[i][j]=="#":
            dp[i][j]=0
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j]

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

Submission status: Accepted

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

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

dp[0][0]=1
for i in range(0,H):
    for j in range(0,W):
        if i!=0 or j!=0:
            if A[i][j]==".":
                ans=0
                if i!=0:
                    ans+=dp[i-1][j]
                if j!=0:
                    ans+=dp[i][j-1]

                dp[i][j]=ans%mod


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

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(H: int, W: int, a: "List[List[str]]"):

    dp = []
    for _ in range(0, H):
        L = [0]*W
        dp.append(L)
    
    # initialize
    for i in range(0, H):
        if a[i][0][0] == "#": 
            break
        dp[i][0] = 1
    for j in range(0, W):
        if a[0][0][j] == "#":
            break
        dp[0][j] = 1

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

    print(dp[H - 1][W - 1] % MOD)
            
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [[next(tokens) for _ in range(1)] for _ in range(H)]  # type: "List[List[str]]"
    solve(H, W, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int,input().split())
#A = [input() for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
mod = 10**9+7

eq = A == '.'

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

for i in range(H):
    for j in range(W):
        if eq[i][j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % mod

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

Submission status: Accepted

Solution code:

import numpy as np

H, W = map(int,input().split())
A = np.array([list(input()) for _ in range(H)], 'U1')
mod = 10**9+7

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MOD = 10**9+7
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

route = [[0]*w for _ in range(h)]
route[1][1] = 1
for i in range(1, h-1):
    for j in range(1, w-1):
        for x, y in [(i+1, j), (i, j+1)]:
            if MAZE[x][y] == '#':
                continue
            route[x][y] += route[i][j]

print(route[-2][-2] % MOD)

Submission status: Accepted

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MOD = 10**9+7
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

route = [[0]*w for _ in range(h)]
route[1][1] = 1
for i in range(1, h-1):
    for j in range(1, w-1):
        for x, y in [(i+1, j), (i, j+1)]:
            if MAZE[x][y] == '#':
                continue
            route[x][y] += route[i][j]
            route[x][y] %= MOD

print(route[-2][-2])

Submission status: Accepted

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MOD = 10**9+7
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

route = [[0]*w for _ in range(h)]
for j in range(1, w):
    if MAZE[1][j] == '.':
        route[1][j] = 1
        continue
    break
for i in range(1, h):
    if MAZE[i][1] == '.':
        route[i][1] = 1
        continue
    break

for i in range(1, h-1):
    for j in range(1, w-1):
        x = i+1
        y = j+1
        if MAZE[x][y] == '#':
            continue
        route[x][y] = route[x-1][y]+route[x][y-1]
        
print(route[-2][-2] % MOD)

Submission status: Accepted

Solution code:
h, w = map(lambda x: int(x)+2, input().split())
MOD = 10**9+7
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

route = [[0]*w for _ in range(h)]
for j in range(1, w):
    if MAZE[1][j] == '.':
        route[1][j] = 1
        continue
    break
for i in range(1, h):
    if MAZE[i][1] == '.':
        route[i][1] = 1
        continue
    break

for i in range(1, h-1):
    for j in range(1, w-1):
        x = i+1
        y = j+1
        if MAZE[x][y] == '#':
            continue
        route[x][y] = route[x-1][y]+route[x][y-1]
        
print(route[-2][-2] % MOD)

Submission status: Accepted

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

dp[0][0] = 1
dp[1][0] = 1 if maze[1][0] != '#' else float('inf')
dp[0][1] = 1 if maze[1][0] != '#' else float('inf')

for i in range(H):
    for j in range(W):
        if 0 <= i+1 < H and 0 <= j+1 < W and maze[i+1][j] != '#':
            dp[i+1][j+1] += dp[i+1][j] % mod
        if 0 <= j+1 < W and 0 <= i+1 < H and maze[i][j+1] != '#':
            dp[i+1][j+1] += dp[i][j+1] % mod
print(dp[H-1][W-1] % mod) if dp[H-1][W-1] != float('inf') else 0
'''
dp[0][0] = 1
'''
dp[0][1] = 1 if dp[0][1] != '#' else '#'
dp[1][0] = 1 if dp[1][0] != '#' else '#'
'''
for i in range(H):
    for j in range(W):
        if dp[i][j] != '#' and j > 0 and isinstance(dp[i][j-1], int):
            if isinstance(dp[i][j], int):
                dp[i][j] += dp[i][j-1] % mod
            else:
                dp[i][j] = dp[i][j-1] % mod
        if dp[i][j] != '#' and i > 0 and isinstance(dp[i-1][j], int):
            if isinstance(dp[i][j],int):
                dp[i][j] += dp[i-1][j] % mod
            else:
                dp[i][j] = dp[i-1][j] % mod
'''
print(dp)
'''
print(dp[H-1][W-1] % mod) if dp[H-1][W-1] != '.' else print(0)

Submission status: Accepted

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

a = [input() for _ in range(h)]
dp=[[0 for i in range(w)] for j in range(h)]
MOD=10**9+7
if a[0][0]==".":
    dp[0][0]=1

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

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

Submission status: Accepted

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

dp = [[0]*(w) for _ in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i+1 < h and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            if 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())
a = [input() for _ in range(h)]
MOD = 10**9+7

dp = [[0]*(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]
            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())
p = 10**9+7
S = []
for i in range(h):
    S.append(list(input()))
A = [[0 for j in range(w)] for i in range(h)]
flag = True
for i in range(h):
    if S[i][0] == '#':
        flag = False
    if flag:
        A[i][0] = 1
flag = True
for j in range(w):
    if S[0][j] == '#':
        flag = False
    if flag:
        A[0][j] = 1
for i in range(1, h):
    for j in range(1, w):
        if S[i][j] == '#':
            A[i][j] = 0
        else:
            A[i][j] = (A[i-1][j]+A[i][j-1]) % p
print(A[h-1][w-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

H,W = LI()
c = [list(S()) for i in range(H)]
dp = FILL(0,H+1,W+1)
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i+1<H:
            if c[i+1][j] == '.':
                dp[i+1][j] += dp[i][j]

        if j+1<W:
            if c[i][j+1] == '.':
                dp[i][j+1] += dp[i][j]

        dp[i][j] %= MOD


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

Submission status: Accepted

Solution code:
MOD = 10**9+7

H, W = map(int, input().split())
dp = []
grid = []

for _ in range(H):
    dp.append([0] * W)
    grid.append(input())

dp[0][0] = 1

for r in range(H):
    for c in range(W):
        if grid[r][c] == "#" or (r == 0 and c == 0):
            continue

        up = dp[r-1][c] if r > 0 else 0
        left = dp[r][c-1] if c > 0 else 0

        dp[r][c] = (up + left) % MOD

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[input() for i in range(h)]
mod=10**9+7
d=[[0]*w for i in range(h)]
d[0][0]=1
for i in range(h):
    for j in range(w):
        if i+1<h and a[i+1][j]==".":
            d[i+1][j]+=d[i][j]
            d[i+1][j]%=mod
        if j+1<w and a[i][j+1]==".":
            d[i][j+1]+=d[i][j]
            d[i][j+1]%=mod
print(d[-1][-1])

Submission status: Accepted

Solution code:
r, c = map(int, input().split())
mat = [input() for _ in range(r)]
dp = [[0]*c for _ in range(r)]
for i in range(c):
    if mat[0][i] == '#':
        break
    dp[0][i] = 1
for i in range(r):
    if mat[i][0] == '#':
        break
    dp[i][0] = 1
for i in range(1, r):
    for j in range(1, c):
        if mat[i][j] != '#':
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10**9 + 7)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mat=[]
dp=[]
dp.append([0]*(w+1))

for i in range(h):
    l=input()
    mat.append(l)
    dp.append([0]*(w+1))

dp[0][1]=1
for i in range(h):
    for j in range(w):
        if mat[i][j]=='.':
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%1000000007
            

print(dp[h][w])

Submission status: Accepted

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

for i in range(h):
    grid.append(input())
    dp.append([0]*w)

dp[-1][-1] = 1

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if grid[i][j] == '#':
            continue

        if i+1 < h and grid[i+1][j] != '#':
            dp[i][j] += dp[i+1][j]
        if j+1 < w and grid[i][j+1] != '#':
            dp[i][j] += dp[i][j+1]

print(dp[0][0] % int(1e9+7))