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} \ldots a_{1, W}  :  a_{H, 1} \ldots a_{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 .

Solution (Python):






"""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):
        
        prev = dp.copy()
        dp = [0] * w
        for j in range(w):
            
            if i + j == 0:
                dp[j] = 1
                continue
            if values[i][j] == "
                
                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")
    
    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

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

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+1)
S[0] = '*'*(W+1)
for h in range(1,H+1):
    S[h] = '*' + input()

dps = [[0]*(W+1) for _ in range(H+1)]
mod = 10**9+7

def dp(h,w):
    if h==1 and w==1:
        return 1
    if S[h][w]=='.':
        return (dps[h-1][w]+dps[h][w-1])%mod
    return 0


def solve():
    for h in range(1,H+1):
        for w in range(1,W+1):
            dps[h][w] = dp(h,w)
    ans = dps[-1][-1]
    return ans
print(solve())

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+1)
S[0] = '*'*(W+1)
for h in range(1,H+1):
    S[h] = '*' + input()

dps = [[0]*(W+1) for _ in range(H+1)]
mod = 10**9+7

def dp(h,w):
    if h==1 and w==1:
        return 1
    if S[h][w]=='.':
        return (dps[h-1][w]+dps[h][w-1])%mod
    return 0


def solve():
    for h in range(1,H+1):
        for w in range(1,W+1):
            dps[h][w] = dp(h,w)
    ans = dps[-1][-1]
    return ans
print(solve())

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(1e9)
mod=int(1e9)+7


n,m=mdata()
matrix = [data() for i in range(n)]
dp=[[0]*m for i in range(n)]
if matrix[0][0]!='
    dp[0][0]=1
for i in range(n):
    for j in range(m):
        if matrix[i][j]=='
            continue
        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])%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [readline().rstrip().decode() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if a[i][j] != '
            if i != h - 1:
                if a[i + 1][j] != '
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j] %= mod
            if j != w - 1:
                if a[i][j + 1] != '
                    dp[i][j + 1] += dp[i][j]
                    dp[i][j + 1] %= mod
print(dp[-1][-1] % mod)

Solution (Python):

def solve(H, W, grid):
	MOD = 10 ** 9 + 7
	dp = [0] * (W)
	for j in range(W):
		if grid[0][j] == '
			break
		if j == 0:
			dp[j] = 1
		else:
			dp[j] = dp[j-1]

	for i in range(1, H):
		dp2 = [0] * W
		dp2[0] = dp[0] if grid[i][0] != '
		for j in range(1, W):
			dp2[j] = dp[j] + dp2[j-1] if grid[i][j] != '
		dp = dp2

	return dp[-1] % MOD

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

Solution (Python):
mod = 10 ** 9 + 7

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

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

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

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

Solution (Python):
h, w = map(int, input().split())
a = [["
a.insert(0, ["
mod = 10 ** 9 + 7
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = 1
for i in range(1, h + 1):
    for j in range(1, 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])

Solution (Python):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())
ans = [[0 for _ in range(w)] for _ in range(h)]
ans[0][0] = 1
mod = 7+10**9
for i in range(h):
    for j in range(w):
        if ans[i][j] == 0 or l[i][j] == "
            continue
        if i+1 < h:
            ans[i+1][j] += ans[i][j]
            ans[i+1][j] %= mod
        if j+1 < w:
            ans[i][j+1] += ans[i][j]
            ans[i][j+1] %= mod
print(ans[-1][-1])

Solution (Python):
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))

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


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)

Solution (Python):
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])

Solution (Python):

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


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)

Solution (Python):

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


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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):






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

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

Solution (Python):






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

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

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = lambda: sys.stdin.readline().rstrip()

H, W = map(int, input().split())
grid = [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 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))

Solution (Python):
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] == '
        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])

Solution (Python):


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

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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[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)

Solution (Python):
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 = 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])

Solution (Python):
import sys
import numpy as np

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

H, W = map(int,input().split())

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

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):

import sys

MOD = 1000000007  


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

    dp = []
    for _ in range(0, H):
        L = [0]*W
        dp.append(L)
    
    
    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



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    a = [[next(tokens) for _ in range(1)] for _ in range(H)]  
    solve(H, W, a)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

H, W = map(int,input().split())

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

Solution (Python):

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

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
import sys
import numpy as np

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

H, W = map(int,input().split())

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

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

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)

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

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

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

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)

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

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)