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):
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(input())
dp = [[0 for i in range(m)] for j in range(n)]
for i in range(m):
    if a[0][i]=='.':
        dp[0][i]=1
    else:
        break
for i in range(n):
    if a[i][0]=='.':
        dp[i][0]=1
    else:
        break
for i in range(1,n):
    for j in range(1,m):
        if a[i][j]=='.':
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
print(dp[-1][-1]%1000000007)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
s = [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 s[i][j] == "
            continue
        if i and s[i-1][j] == ".":
            dp[i][j] += dp[i-1][j]
        if j and s[i][j-1] == ".":
            dp[i][j] += dp[i][j-1]
        dp[i][j] %=mod

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

Solution (Python):
from collections import deque

mod = 10**9+7

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

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

D = deque()
D.append((0, 0))

dxdy = [(0, 1), (1, 0)]

appended =  [[False]*w for _ in range(h)]
appended[0][0] = True
while D:
  p = D.popleft()
  if p == (h-1, w-1):
    break
  for k in range(2):
    nx = p[0] + dxdy[k][0]
    ny = p[1] + dxdy[k][1]
    if 0<=nx<h and 0<=ny<w and maze[nx][ny]==".":
      cnt[nx][ny] += cnt[p[0]][p[1]]
      cnt[nx][ny] %= mod
      if appended[nx][ny]==False:
        D.append((nx, ny))
        appended[nx][ny] = True

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

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

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

print(dp(0,0)%mod)

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

print(dp(0,0)%mod)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


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


def DD(arg): return defaultdict(arg)


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


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

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

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


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


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


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


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


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


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


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

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

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


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





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

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

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

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

Solution (Python):
n , m = map(int , input().split())
dp = []
for i in range(n + 1):
    dp.append([])
    for j in range(m + 1):
        dp[i].append(0)
arr = []
for i in range(n):
    arr.append(input())
dp[1][1] = 1
for i in range(1,n + 1):
    for j in range(1,m + 1):
        if arr[i - 1][j - 1] == '
            continue
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m] % 1000000007)

Solution (Python):
H,W = map(int,input().split())
MOD = 10 ** 9 + 7

grid = [""] * H
for i in range(H):
  grid[i] = input()
  
dp = [[0] * W for i in range(H)]
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]
      dp[i + 1][j] %= MOD
    if j + 1 < W and grid[i][j + 1] != "
      dp[i][j + 1] += dp[i][j]
      dp[i][j + 1] %= MOD
      
print(dp[-1][-1])

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]

MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,n,m):
    dp = list2d(n,m,0)
    for i in range(1,n): 
        if A[i][0]== '.':
            dp[i][0] = 1
        else:
            break
    for j in range(1,m): 
        if A[0][j] == '.':
            dp[0][j] = 1
        else:
            break
    dp[0][0] = 1
    for i in range(1,n):
        for j in range(1,m):
            if A[i][j] == "
                dp[i][j] = 0
                continue
            if A[i-1][j] == '.':
                dp[i][j] += dp[i-1][j]
                dp[i][j] %= MOD
            if A[i][j-1] == '.':
                dp[i][j] += dp[i][j-1]
                dp[i][j] %= MOD
    return int(dp[n-1][m-1])
        
H,W = ilele()
A = []
for i in range(H):
    B = [*input()]
    A.append(B.copy())
print(fun(A,H,W))

Solution (Python):





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

l = []
for val in range(h):
    l.append(input())
    
    
ans = [[0 for j in range(w)] for i in range(h)]


ans[0][0] =  1

for i in range (h):
    for j in range (w):
        
        if l[i][j]=="
            continue
        if l[i][j] == '.':
            ans[i][j] += (ans[i-1][j] % 1000000007)+(ans[i][j-1] % 1000000007)
print(ans[h-1][w-1] % 1000000007)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)


n, m = list(map(int, input().split()))
a = ["" for i in range(n)]

N = 10**9 + 7

for i in range(n):
    a[i] = str(input())

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

flag = 0
for i in range(n):
    if a[i][0] == "
        dp[i][0] = 0
        flag = 1
    else:
        dp[i][0] = 1

flag = 0
for j in range(m):
    if a[0][j] == "
        dp[0][j] = 0
        flag = 1
    else:
        dp[0][j] = 1

for i in range(1,n):
    for j in range(1,m):
        if a[i][j] == "
            dp[i][j] = 0
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % N

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

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

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

for i in range(1,H):
	if a[i][0]=='
		dp[i][0] = 0
	else:
		dp[i][0] = dp[i-1][0]

for j in range(1,W):
	if a[0][j]=='
		dp[0][j] = 0
	else:
		dp[0][j] = dp[0][j-1]

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

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

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

for x in range(1,W+1):
    for y in range(1,H+1):
        if x == y == 1:
            continue
        else:
            if A[y-1][x-1] != '
                dp[y][x] = dp[y-1][x] + dp[y][x-1]
print(dp[H][W] % mod)

Solution (Python):




from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

h, w = iia()
arr = []
for i in range(h):
    arr.append(list(is1()))
dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i > 0 and j > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        elif i > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i - 1][j]
        elif j > 0 and arr[i][j] == '.':
            dp[i][j] = dp[i][j - 1]
print(dp[-1][-1] % mod)

Solution (Python):
H,W = map(int, input().split())
M = 10**9 + 7
A = []
for _ in range(H):
  S = input()
  A.append(S)
L = [[0 for j in range(W)] for i in range(H)]
L[0][0] =  1
for i in range (H):
  for j in range (W):
    if A[i][j] == '.':
        if i > 0:
            L[i][j] += L[i-1][j] % M
        if j > 0:
            L[i][j] += L[i][j-1] % M
print(L[H-1][W-1] % M)

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '
S[H+1] = '
for h in range(1,H+1):
  S[h] = '
mod = 10**9+7
dp = [[0]*(W+1) for _ in range(H+1)]
dp[1][1] = 1
for h in range(1,H+1):
  for w in range(1,W+1):
    if h==1 and w==1:
      continue
    if S[h][w]=='
      continue
    dp[h][w] += dp[h][w-1]+dp[h-1][w]
    dp[h][w] %= mod
print(dp[-1][-1])

Solution (Python):

def mod(num):
    return num % (10 ** 9 + 7)

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

for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "
            dp[i][j] = -1

dp[0][0] = 1

for col in range(1, W):
    if dp[0][col] != -1:
        dp[0][col] = dp[0][col - 1]
    else:
        dp[0][col] = 0

for row in range(1, H):
    for col in range(W):
        if dp[row][col] != -1:
            if col == 0:
                dp[row][col] = dp[row - 1][col]
            else:
                dp[row][col] = mod(dp[row - 1][col] + dp[row][col - 1])
        else:
            dp[row][col] = 0

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

Solution (Python):

def mod(num):
    return num % (10 ** 9 + 7)

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

for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "
            dp[i][j] = -1

dp[0][0] = 1

for col in range(1, W):
    if dp[0][col] != -1:
        dp[0][col] = dp[0][col - 1]
    else:
        dp[0][col] = 0

for row in range(1, H):
    for col in range(W):
        if dp[row][col] != -1:
            if col == 0:
                dp[row][col] = dp[row - 1][col]
            else:
                dp[row][col] = mod(dp[row - 1][col] + dp[row][col - 1])
        else:
            dp[row][col] = 0

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

Solution (Python):










def mod(num):
    return num % (10 ** 9 + 7)

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

for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "
            dp[i][j] = -1

dp[0][0] = 1
for row in range(H):
    for col in range(W):
        if row != 0 or col != 0:
            if row == 0:
                if dp[row][col] != -1:
                    dp[row][col] = dp[row][col - 1]
                else:
                    dp[row][col] = 0
            elif col == 0:
                if dp[row][col] != -1:
                    dp[row][col] = dp[row - 1][col]
                else:
                    dp[row][col] = 0
            else:
                if dp[row][col] != -1:
                    dp[row][col] = mod(dp[row - 1][col] + dp[row][col - 1])
                else:
                    dp[row][col] = 0

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

Solution (Python):

"""
Created on Sun Jul 26 15:42:52 2020

@author: tinku
"""
def converter(arr,m,n):
    new_arr=[[0 for i in range(n)] for j in range(m)]
    for i in range(m):
        for j in range(n):
            if arr[i][j]=='.':
                new_arr[i][j]=0
            else:
                new_arr[i][j]=1
    return new_arr
            
m,n=map(int,input().split())
arr=[]
for i in range(m):
    arr.append(input())
arr=converter(arr,m,n)
if arr[0][0]==1 or arr[m-1][n-1]==1:
    print(0)
else:
    arr[0][0]=1
    for i in range(1,m):
        arr[i][0]=int(arr[i-1][0]==1 and arr[i][0]==0)
    for i in range(1,n):
        arr[0][i]=int(arr[0][i-1]==1 and arr[0][i]==0)
    for i in range(1,m):
        for j in range(1,n):
            if arr[i][j]==0:
                arr[i][j]=arr[i-1][j] + arr[i][j-1]
            else:
                arr[i][j]=0
    print((arr[m-1][n-1])%(10**9 +7))

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

Solution (Python):
NUM=10**9+7
H,W=list(map(int,input().split()))
matrix=[]
for i in range(H):
    matrix.append(list(input()))
dp=[[0]*W for i in range(H)]
dp[0][0]=1
for i in range(1,W):
    if(matrix[0][i]=='
        dp[0][i]=0
    else:
        dp[0][i]=dp[0][i-1]
for j in range(1,H):
    if(matrix[j][0]=='
        dp[j][0]=0
    else:
        dp[j][0]=dp[j-1][0]
for i in range(1,H):
    for j in range(1,W):
        if(matrix[i][j]=='
            dp[i][j]=0
        else:
            dp[i][j]=(dp[i-1][j] + dp[i][j-1])%NUM 
print(dp[H-1][W-1]%NUM)

Solution (Python):
from sys import stdin
h,w = map(int,stdin.readline().split())
arr = [list(stdin.readline()) for _ in range(h)]
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
mod = 10**9+7
for i in range(h):
    for j in range(w):
        if arr[i][j] == '.':
            dp[i][j] += (0 if i==0 else dp[i-1][j])+(0 if j==0 else dp[i][j-1])
            dp[i][j] %= mod
print(dp[-1][-1])

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    dp = [[0 for _ in range(w)] for __ in range(h)]
    dp[0][0] = 1

    def calc(x, y, val):
        if x >= w or y >= h:
            return
        if mat[y][x] == "
            return
        dp[y][x] += val
        dp[y][x] %= MOD
        return

    for y in range(h):
        for x in range(w):
            calc(x + 1, y, dp[y][x])
            calc(x, y + 1, dp[y][x])
    print(dp[h - 1][w - 1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    dp = [[0 for _ in range(w)] for __ in range(h)]
    dp[0][0] = 1

    def calc(x, y, val):
        if x >= w or y >= h:
            return
        if mat[y][x] == "
            return
        dp[y][x] += val
        dp[y][x] %= MOD
        return

    for y in range(h):
        for x in range(w):
            calc(x + 1, y, dp[y][x])
            calc(x, y + 1, dp[y][x])
    print(dp[h - 1][w - 1])


if __name__ == '__main__':
    main()

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

Solution (Python):
H,W = map(int,input().split())
mod = 10**9 + 7
grid_0 = [0] * (W+1)
grid_0[1] = 1

for n in range(1,H+1):
  grid_1 = [0] * (W+1)
  for i, j in enumerate(input(), 1):
    if j == ".":
      grid_1[i] = (grid_0[i] + grid_1[i-1]) % mod
  grid_0 = grid_1

print(grid_0[-1])

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

MOD = 10**9 + 7
dp = [[0]*W for _ in range(H)]

for i in range(H):
  grid = input()
  if i == 0:
    Flag = True
    for j in range(W):
      if grid[j] == "
        Flag = False
      if Flag:
        dp[i][j] = 1
      else:
        dp[i][j] = 0
  else:
    for j in range(W):
      if grid[j] == "
        dp[i][j] = 0
      else:
        if 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])

Solution (Python):
H, W = map(int, input().split())
m = 10**9+7
index_lst = []
grid_0 = [0] * (W+1)
grid_0[1] = 1
for _ in range(1, H+1):
  grid_1 = [0] * (W+1)
  for i, j in enumerate(input(), 1):
    if j == '.':
      grid_1[i] = (grid_0[i] + grid_1[i-1]) % m
  grid_0 = grid_1
    
print(grid_0[-1])

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

h, w = map(int,input().split())
C = [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!=0 or j!=0) and C[i][j]==".":
            if i-1 >= 0:
                D[i][j] += D[i-1][j]
            if j-1 >= 0:
                D[i][j] += D[i][j-1]
            D[i][j] %= mod
print(D[-1][-1])

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    a = [input() for _ in range(H)]
    m = 10**9 + 7

    dp = [0] * W
    for i in range(H):
        for j in range(W):
            if i == j == 0:
                dp[j] = 1
                continue
            if a[i][j] == '.':
                if j > 0:
                    dp[j] = (dp[j] + dp[j-1]) % m
            else:
                dp[j] = 0
    print(dp[W-1])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    H,W=map(int,input().split())
    maze=[]
    for _ in range(H):
        a=input().rstrip()
        maze.append(a)
    path=[[0]*W for _ in range(H)]
    path[0][0]=1
    q=deque([[0,0]])
    finished=[[False]*W for _ in range(H)]
    while q:
        h,w=q.popleft()
        if finished[h][w]==True:
            continue
        for nh,nw in ([h+1,w],[h,w+1]):
            if nh<0 or nh>H-1 or nw<0 or nw>W-1:
                continue
            if maze[nh][nw]=="
                continue
            path[nh][nw]+=path[h][w]
            path[nh][nw]%=1000000007
            q.append([nh,nw])
        finished[h][w]=True
    print(path[-1][-1])

if __name__=="__main__":
    main()

Solution (Python):
r,c=map(int,input().split())
mod=10**9+7
g=[]
for _ in range(r):
  g.append(input())
dp=[[0 for j in range(c)] for i in range(r)]
dp[0][0]=1
for i in range(r):
  for j in range(c):
    if g[i][j]=='.':
        if i>0:
            dp[i][j]+=dp[i-1][j]%mod
        if j>0:
            dp[i][j]+=dp[i][j-1]%mod


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

Solution (Python):

def resolve():
    MOD = 10 ** 9 + 7
    H, W = map(int, input().split())
    G = [list(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 i + 1 < H and G[i + 1][j] == ".":
                dp[i + 1][j] += dp[i][j]
                dp[i + 1][j] %= MOD
            if j + 1 < W and G[i][j + 1] == ".":
                dp[i][j + 1] += dp[i][j]
                dp[i][j + 1] %= MOD
    print(dp[H-1][W-1])


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys

readline = sys.stdin.readline
n, m = map(int, readline().split())
grid = []
for _ in range(n):
    row = readline()
    real_row = [c for c in row if c != "\n"]
    grid.append(real_row)
dp = []
sys.setrecursionlimit(10**7)

for _ in range(n):
    temp = []
    for j in range(m):
        temp.append(-1)
    dp.append(temp)


def traverse(i, j):
    path = 0
    if i < n-1 and j < m-1:
        if dp[i][j] != -1:
            return dp[i][j]
    if i == n - 1 and j == m - 1:
        return 1
    elif i == n - 1:
        if grid[i][j + 1] != "
            path += traverse(i, j + 1)
    elif j == m - 1:
        if grid[i + 1][j] != "
            path += traverse(i + 1, j)
    else:
        if grid[i + 1][j] != "
            path += traverse(i + 1, j)
        if grid[i][j + 1] != "
            path += traverse(i, j + 1)
    dp[i][j] = path
    return path % (10 ** 9 + 7)


print(traverse(0, 0))

Solution (Python):
import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
DIV = 10 ** 9 + 7
G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

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

for i in range(H):
  for j in range(W):
    if G[i][j] == "
      dp[i + 1][j + 1] = 0
    else:
      dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
      dp[i + 1][j + 1] %= DIV
      
print(dp[-1][-1])

Solution (Python):
MOD = 1000000007
h,w=map(int,input().split())
graph=[]
for i in range(h):
  graph.append(list(input()))

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

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

Solution (Python):
h, w = map(int, input().split())
a = [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 a[i][j] == '.':
            if i < h - 1:
                dp[i+1][j] = dp[i][j]
            if j < w - 1:
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % 1000000007
print(dp[h-1][w-1])

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

dp = [[0]*1100 for _ in range(1100)]
dp[1][1] = 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if h == 1 and w == 1:
            continue
        if a[h-1][w-1] == '
            dp[h][w] = 0
        else:
            dp[h][w] += (dp[h-1][w] + dp[h][w-1]) % MOD
print(dp[H][W] % MOD)

Solution (Python):
h,w=map(int,input().split())
m=10**9+7
arr=[[1 for j in range(w)]for i in range(h)]
for i in range(h):
  string=input()
  for j in range(w):
    if string[j]=="
      arr[i][j]=0

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 i>0 and arr[i-1][j]:
      dp[i][j]=(dp[i][j]+dp[i-1][j])%m
    if j>0 and arr[i][j-1]:
      dp[i][j]=(dp[i][j]+dp[i][j-1])%m
print(dp[h-1][w-1]%m)

Solution (Python):
MOD = 1000000007

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

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

for i in range(1, H):
    if A[i][0] == '.':
        dp[i][0] = dp[i - 1][0]

for j in range(1, W):
    if A[0][j] == '.':
        dp[0][j] = dp[0][j - 1]

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

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

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    
    
    

    H, W = map(int, input().split())
   
    dp = [[0]*W for i in range(H)]
    route = []
    for h in range(H):
        As = input().strip()
        route.append(As)

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                dp[h][w] = 1
                continue
            if h > 0 and route[h-1][w] != '
                dp[h][w] += dp[h-1][w]
            if w > 0 and route[h][w-1] != '
                dp[h][w] += dp[h][w-1]

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


if __name__ == '__main__':
    main()

Solution (Python):
v=pow(10,9)+7
arr=[]
inp = list(map(int,input().split()))
row=inp[0]
col=inp[1]
for i in range(row):
    s=input()
    arr.append(s)
ans=[[0 for i in range(col)]for j in range(row)]
for i in range(col):
    if arr[0][i]=='
        break
    else:
        ans[0][i]=1
for i in range(row):
    if arr[i][0]=='
        break
    else:
        ans[i][0]=1
for i in range(1,row):
    for j in range(1,col):
        if arr[i][j]=='
            continue
        else:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1])%v
print (ans[-1][-1])

Solution (Python):
n , m = map(int , input().split())
dp = []
for i in range(n + 1):
    dp.append([])
    for j in range(m + 1):
        dp[i].append(0)
arr = []
for i in range(n):
    arr.append(input())
dp[1][1] = 1
for i in range(1,n + 1):
    for j in range(1,m + 1):
        if arr[i - 1][j - 1] == '
            continue
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m] % 1000000007)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)





def input():
    return sys.stdin.readline().rstrip()


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

    dp = [[0] * W] * H
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                dp[i][j] = 1
                continue
            if A[i][j] == "
                dp[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][j - 1] + dp[i - 1][j]) %mod

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

    pass


if __name__ == "__main__":
    main()