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


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







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)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)



def solve():
    h,w=sep()
    N=10**9 +7
    ar=[]
    for i in range(h):
        ar.append([i for i in inp().strip()])
    dp=[[0 for i in range(w+5)] for _ in range(h+5)]
    dp[0][0]=1
    for i in range(1,h):
        if ar[i][0]==".":
            dp[i][0]=1
        else:
            break
    for i in range(1,w):
        if ar[0][i]==".":
            dp[0][i]=1
        else:
            break
    for i in range(1,h):
        for j in range(1,w):
            if ar[i][j]=="
                dp[i][j]=0
                continue
            else:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%N

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


solve()

Solution (Python):

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(1000000)


INF = float("inf")

d = deque()


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

a = [["
memo = [[0 for _ in [INF] * (w + 1)] for _ in [INF] * ((h + 1))]

for i in range(h + 1)[1:]:
    a[i] = list("

memo[1][1] = 1
d = deque()
if a[2][1] == ".":
    d.append((2, 1))
if a[1][2] == ".":
    d.append((1, 2))


def dp(x, y):
    tmp = 0
    if a[x - 1][y] == ".":
        tmp = tmp + memo[x - 1][y]
    if a[x][y - 1] == ".":
        tmp = tmp + memo[x][y - 1]
    tmp = tmp % (10 ** 9 + 7)
    memo[x][y] = tmp
    return tmp


while len(d) > 0:
    x, y = d.popleft()
    if memo[x][y] == 0:
        dp(x, y)
        if x < h:
            if a[x + 1][y] == ".":
                d.append((x + 1, y))
        if y < w:
            if a[x][y + 1] == ".":
                d.append((x, y + 1))


ans = memo[h][w]

print("{}".format(ans))

Solution (Python):
def solve(n,m,ar):
    mod = int(1e9) + 7
    dp = [[0] * (m+2) for _ in range(n+2)]
    dp[1][1] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if ar[i][j] == "
            if i == 1 and j == 1: continue
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod

    print(dp[n][m])



if __name__ == '__main__':
    n,m = map(int,input().split())

    ar = [[-1] * (m+2) for i in range(n+2)]

    for i in range(1,n+1):
        temp = list(input())
        for j in range(1,m+1):
            ar[i][j] = temp[j-1]

    solve(n,m,ar)

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

grid[0][0]=1
for i in range(1,h):
	if(grid[i-1][0]==0):
		grid[i][0]=0
	elif(grid[i][0]=='
		grid[i][0]=0
	else:
		grid[i][0]=grid[i-1][0]
for i in range(1,w):
	if(grid[0][i-1]==0):
		grid[0][i]=0
	elif(grid[0][i]=='
		grid[0][i]=0
	else:
		grid[0][i]=grid[0][i-1]

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

Solution (Python):
n,m=list(map(int,input().split()))
l=[]
for i in range(n):
    a=input()
    p=[]
    for i in range(m):
        if a[i]=='
            p.append(-1)
        else:
            p.append(0)
    l.append(p)
dp=[[0 for j in range(m)]for i in range(n)]
for i in range(m):
    if l[0][i]!=-1:
        dp[0][i]=1
    else:
        break
for i in range(n):
    if l[i][0]!=-1:
        dp[i][0]=1
    else:
        break
mod=10**9+7
for i in range(1,n):
    
    for j in range(1,m):
        if l[i][j]!=-1:
            
            
                
                
                
            
            dp[i][j]+=((dp[i-1][j])%(mod) + (dp[i][j-1])%mod)%mod
        

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

Solution (Python):
h, w = map(int, input().split(" "))
dp = [[0 for i in range(w)] for j in range(h)]
mod=1e9+7
for i in range(h):
    s = input()
    for j in range(w):
        if i==0 and j==0:
            dp[0][0]= 1 if (s[j]=='.') else 0
        elif i==0:
            dp[0][j]= dp[0][j-1] if (s[j]=='.') else 0
        elif j==0:
            dp[i][0]= dp[i-1][0] if (s[0]=='.') else 0
        else:
            dp[i][j]= (dp[i-1][j]%mod+dp[i][j-1]%mod)%mod if s[j]=='.' else 0
print(int(dp[h-1][w-1]%mod))

Solution (Python):
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

prime = 10**9 + 7

def get(i, j, m, value):
    if i==h-1 and j==w-1:
        return 1
    if value[i][j]!=-1:
        return value[i][j]
    ans = 0
    if i < h-1 and m[i+1][j]=='.':
        value[i+1][j] = get(i+1, j, m, value)
        ans += value[i+1][j]
    if j < w-1 and m[i][j+1]=='.':
        value[i][j+1] = get(i, j+1, m, value)
        ans += value[i][j+1]
    return ans%prime

h, w = map(int,input().split())
m = []
for i in range(h):
    m.append(input())
value = [[-1 for i in range(w)] for j in range(h)]
ans = get(0, 0, m, value)
print(ans)

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

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]

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

dp[0][0]=1

judge1=1
judge2=1
for i in range(1,h):
  if maze[i][0]=='
    judge1=0
  dp[i][0]=judge1
    
for i in range(1,w):
  if maze[0][i]=='
    judge2=0
  dp[0][i]=judge2
    
for i in range(1,h):
  for j in range(1,w):
    if maze[i][j]=='
      dp[i][j]=0
    else:
      dp[i][j]=dp[i-1][j]+dp[i][j-1]
      dp[i][j]%=mod
      

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

Solution (Python):
from collections import deque

H,W=map(int,input().split())
mod=10**9+7
S=[]
for i in range(H):
  S.append(input())
  
total = [[0 for i in range(W)] for j in range(H)]
total[0][0] = 1

now = (0,0)
for i in range(H):
  for j in range(W):
    if S[i][j] == '
    if i > 0 and S[i-1][j] != '
      total[i][j] += total[i-1][j]
    if j > 0 and S[i][j-1] != '
      total[i][j] += total[i][j-1]
    total[i][j] %= mod
        
print(total[-1][-1]%mod)

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time

starttime = time.time()

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    
except:
    pass


n,m=L()
A=[input() for i in range(n)]
dp=[[0 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if i==0 and j==0:
            dp[i][j]=1
            continue
        if i==0:
            if A[i][j]==".":
                dp[i][j]=dp[i][j-1]
        elif j==0:
            if A[i][j]==".":
                dp[i][j]=dp[i-1][j]
        else:
            if A[i][j]==".":
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
            else:
                dp[i][j]=0
    
print(dp[-1][-1])



endtime = time.time()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def ints(): return list(map(int, readline().split()))


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7

import numpy as np
H, W = ints()
A = np.array(read_map_as(H))


from numba import njit


@njit('(i8,i8,i8[:,:])', cache=True)
def solve(H, W, A):
    dp = np.zeros((H, W), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(H):
        for j in range(W):
            if A[i, j] == 0:
                if i > 0:
                    dp[i, j] += dp[i - 1, j]
                if j > 0:
                    dp[i, j] += dp[i, j - 1]
                dp[i, j] %= MOD
    print(dp[H - 1, W - 1])


solve(H, W, A)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def ints(): return list(map(int, readline().split()))


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7

import numpy as np
H, W = ints()
A = np.array(read_map_as(H))


from numba import njit


@njit('(i8,i8,i8[:,:])', cache=True)
def solve(H, W, A):
    dp = np.zeros((H, W), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(H):
        for j in range(W):
            if A[i, j] == 1:
                dp[i, j] = 0
                continue
            if i > 0:
                dp[i, j] += dp[i - 1, j]
            if j > 0:
                dp[i, j] += dp[i, j - 1]
            dp[i, j] %= MOD
    print(dp[H - 1, W - 1])


solve(H, W, A)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
a = [ input().rstrip() for _ in range(H)]
dp = [[0]*(W) for _ in range(H)]
dp[0][0]=1
m=10**9+7
for ih in range(H):
    for iw in range(W):
        if a[ih][iw] == '
            dp[ih][iw] = 0
        else:
            if ih>0 and dp[ih-1][iw] >0:
                dp[ih][iw] += dp[ih-1][iw]
                dp[ih][iw] %=m
            if iw>0 and dp[ih][iw-1] >0:
                dp[ih][iw] += dp[ih][iw-1]
                dp[ih][iw] %=m
print(dp[-1][-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def recursive(i,j):
    if i<0 or j<0 or i>=row or j>=col or  grid[i][j]=='
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if i==row-1 and j==col-1:
        return 1
    mod=10**9+7
    dp[i][j]=recursive(i+1,j)%mod +recursive(i,j+1)%mod
    return dp[i][j]%mod


row,col=map(int,input().split())
dp=[[-1]*col for _ in range(row)]
grid=[]
for _ in range(row):
    grid.append(input())
print(recursive(0,0))

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

dp=[[0 for i in range(W+1)] for j in range(H+1)]
dp[0][1]=1
for i in range(1,W+1):
    for j in range(1,H+1):
        if a[j-1][i-1]=='.':
            dp[j][i]=dp[j-1][i]+dp[j][i-1]
print((dp[-1][-1])%(10**9+7))

Solution (Python):
n, m= list(map(int,input().split()))
arr = []
for i in range(n):
    arr.append(list(input()))
dp = []
dp.append([0]*(m+1))
for i in range(n):
    dp.append([0]+[1]*(m))
dp[1][1] = 1
for i in range(n):
    for g in range(m):
        dp[1][1] = 1
        if arr[i][g] != "
            dp[i+1][g+1] = (dp[i][g+1]+dp[i+1][g])%1000000007
        else:
            dp[i+1][g+1] = 0
print(dp[n][m])

Solution (Python):
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    mod = 10**9+7
    h, w = mi()
    g = [[] for _ in range(h+1)]
    g[0] = '
    for i in range(h):
        g[i+1] = '
    dp = np.zeros((h+1, w+1), dtype=int)
    dp[1][1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            if g[i][j] == '
                dp[i][j] = 0
                continue
            dp[i][j] = max(dp[i][j], dp[i-1][j]+dp[i][j-1])
            dp[i][j] %= mod
    print(dp[h][w])
            
            

    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())

maze=[[i for i in input()] for _ in range(h)]

que=deque([[0,0]])

visited=[[0 for _ in range(w)] for _ in range(h)]
visited[0][0]=1

while que:
    n=que.popleft()
    x,y=n[0],n[1]

    if n==(h-1,w-1):
        break

    for i, j in [(1,0), (0,1)]:
        if (x+i >=w) or (y+j >=h) or maze[y+j][x+i] == '
            continue
        if visited[y+j][x+i] == 0:
            que.append([x+i,y+j])
        visited[y+j][x+i] += visited[y][x]

print(visited[h-1][w-1]%(10**9+7))

Solution (Python):
H, W = map(int, input().split())
grid = [list('
for _ in range(1, H+1):
    temp = list(input())
    temp = ['
    grid.append(temp)
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][1] = 1
mod = 10**9 + 7

for i in range(1, H+1):
    for j in range(1, W+1):

        if grid[i][j] == '.':
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= mod
            
print(dp[H][W])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    h, w = map(int, input().split())
    grid = [None]*h
    for i in range(h):
        grid[i] = input()
    
    mod = pow(10, 9)+7
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            dp[i][j] %= mod
            if i != h-1 and grid[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
            if j != w-1 and grid[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
    
    print(dp[h-1][w-1])
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    h, w = map(int, input().split())
    grid = [None]*h
    for i in range(h):
        grid[i] = input()
    
    mod = pow(10, 9)+7
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            dp[i][j] %= mod
            if i != h-1 and grid[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
            if j != w-1 and grid[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
    
    print(dp[h-1][w-1])
    
if __name__ == "__main__":
    main()

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

grid = [input() for _ in range(H)]


dp = [[0 for _ in range(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 not (i == 1 and j == 1):
            if grid[i - 1][j - 1] == "
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % (10**9 + 7)


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

Solution (Python):
h, w = map(int, input().split())
A = [input() for _ in range(h)]
mod = 10**9 + 7
memo = [[0] * w for _ in range(h)]
for i in range(h):
    if A[i][0] == '.':
        memo[i][0] = 1
    else:
        break
for j in range(w):
    if A[0][j] == '.':
        memo[0][j] = 1
    else:
        break
for i in range(1, h):
    for j in range(1, w):
        if A[i][j] == '
            memo[i][j] = 0
        else:
            memo[i][j] = (memo[i-1][j] + memo[i][j-1]) % mod
print(memo[-1][-1])

Solution (Python):
h, w = map(int, input().split())
A = [input() for _ in range(h)]
mod = 10**9 + 7
memo = [[0] * w for _ in range(h)]
for i in range(h):
    if A[i][0] == '.':
        memo[i][0] = 1
    else:
        break
for j in range(w):
    if A[0][j] == '.':
        memo[0][j] = 1
    else:
        break
for i in range(1, h):
    for j in range(1, w):
        if A[i][j] == '
            memo[i][j] = 0
        else:
            memo[i][j] = (memo[i-1][j] + memo[i][j-1]) % mod
print(memo[-1][-1])

Solution (Python):
mod = 1000000007

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

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

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

Solution (Python):
mod = 1000000007

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

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if (h != 0 or w != 0) and root[h][w] == '.':
            dp[h][w] = (dp[h-1][w] + dp[h][w-1])%mod

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
H, W = map(int, input().split())
a = [list(input()) for i in range(H)]
dp = [[0]*(W+1) for i in range(H+1)]
dp[0][1] = 1
mod = 10**9 + 7
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-1][j] + dp[i][j-1]
            dp[i][j] %= mod
            
ans =dp[H][W]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

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

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        dp[i][j] %= MOD
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
print(dp[h-1][w-1])

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        dp[i][j] %= MOD
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
print(dp[h-1][w-1])

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
        dp[i][j] %= MOD
print(dp[h-1][w-1])

Solution (Python):
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0] * 1050 for _ in range(1050)]
MOD = int(1e9+7)
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i + 1 < h and grid[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
        if j + 1 < w and grid[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
        dp[i][j] %= MOD
print(dp[h-1][w-1])

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



def f(y, x):
    if dp[y][x] != -1:
        return dp[y][x]
    res = 0
    if x == W:
        res = f(y + 1, x)
    elif y == H:
        res = f(y, x + 1)
    else:
        res = f(y, x + 1) + f(y + 1, x)
    dp[y][x] = res
    return res


dp[H][W] = 1
for i in reversed(range(1, H + 1)):
    for j in reversed(range(1, W + 1)):
        
        if a[i-1][0][j-1] == '
            dp[i][j] = 0
        else:
            f(i, j)
print(dp[1][1]%1000000007)

Solution (Python):
n, m = map(int, input().split())

grid = [None]*n
mod = 10**9+7

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

dp = [[0]*m for _ in range(n)]

dp[0][0] = 1

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

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

for i in range(1, n):
    for j in range(1, m):
        if grid[i][j] == '
            continue

        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod

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

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*w for i in range(h)] 
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="
            lis[i][j]=1
dp=[[0]*w for i in range(h)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        if lis[i][j]==1:
            continue
        else:
            if i==j==0:
                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])%mod

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

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="
            lis[i][j]=1

Q=deque([[0,0]])
dp=[[-1]*w for i in range(h)]
dp[0][0]=1
step=[[1,0],[0,1]]
while Q:
    x,y=Q.popleft()
    for i,j in step:
        if x+i>=h or y+j>=w:
            continue
        if lis[x+i][y+j]==1:
            continue
        if dp[x+i][y+j]<0:
            dp[x+i][y+j]=dp[x][y]%mod
            Q.append([x+i,y+j])
        else:
            dp[x+i][y+j]+=dp[x][y]%mod
    
print(max(0,dp[-1][-1])%mod)

Solution (Python):


INF = float('inf')
M = 10 ** 9 + 7


def tc():
    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 j in range(w):
            if grid[i][j] == '
                continue
            if i > 0:
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % M
            if j > 0:
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % M

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


tc()

Solution (Python):
H,W=list(map(int, input().split()))
G=[['
for i in range(H):
    G.append(['

C=10**9+7






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

for i in range(H):
    for j in range(W):
        if G[i+1][j+1]=='
            continue
        if G[i][j+1]!='
            dp[i][j]+=dp[i-1][j]
            dp[i][j]%=C
        if G[i+1][j]!='
            dp[i][j]+=dp[i][j-1]
            dp[i][j]%=C
    
print(dp[H-1][W-1])

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

mod = 10**9 + 7


def main():

    H, W = in_nn()
    grid = in_map2(H)

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

    for y in range(H):
        for x in range(W):
            if x + 1 < W and grid[y][x + 1]:
                dp[y][x + 1] += dp[y][x]
                dp[y][x + 1] %= mod
            if y + 1 < H and grid[y + 1][x]:
                dp[y + 1][x] += dp[y][x]
                dp[y + 1][x] %= mod

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


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9 + 7
H, W = list(map(int, input().split()))
grid = [[1]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '
            grid[h][w] = 0

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


dp[0][0] = 1
for h in range(1, H):
    if grid[h][0]:
        dp[h][0] = dp[h-1][0]
for w in range(1, W):
    if grid[0][w]:
        dp[0][w] = dp[0][w-1]


for h in range(1, H):
    for w in range(1, W):
        if grid[h][w]:
            dp[h][w] = (dp[h-1][w] + dp[h][w-1])%mod
print(dp[-1][-1])

Solution (Python):
mod = 1000000007
from sys import setrecursionlimit

setrecursionlimit(100000)


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


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


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

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