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):
ROUTE, WALL = 0, 1
def main():
    H, W = [int(n) for n in input().split()]
    H, W = H+1, W+1
    grid = [[ROUTE]*W for i in range(H)]
    for h in range(H):
        if h == 0:
            grid[0] = [WALL] * W
            continue
        instr = "
        for w, c in enumerate(instr):
            grid[h][w] = ROUTE if c == "." else WALL
    dp = [-1]*(H*W)
    dp[coord_to_num(W, 1,1)]=1
    for crd in range(H*W):
        if dp[crd] != -1:
            continue
        h, w = num_to_coord(W, crd)
        if grid[h][w] == WALL:
            dp[crd] = 0
            continue
        up = dp[coord_to_num(W,h-1, w)]
        down = dp[coord_to_num(W, h, w-1)]
        dp[coord_to_num(W, h, w)] = up+down
    print(dp[coord_to_num(W, H-1, W-1)] % (10 ** 9 + 7))


def num_to_coord(W, num):
    return (num//W, num%W)
def coord_to_num(W, h, w):
    return h * W + w

if __name__ == "__main__":
    main()

Solution (Python):
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
dp = [[0] * w for i in range(h)]
dp[0][0] = 1
for i in range(h):
  for j in range(w):
    if i == 0:
      if j != 0:
        if lis[i][j] == "." and lis[i][j-1] == ".":
          dp[i][j] += dp[i][j-1]
    elif j == 0:
      if i != 0:
        if lis[i][j] == "." and lis[i-1][j] == ".":
          dp[i][j] += dp[i-1][j]
    else:
      if lis[i][j] == "." and lis[i][j-1] == ".":
        dp[i][j] += dp[i][j-1]
      if lis[i][j] == "." and lis[i-1][j] == ".":
        dp[i][j] += dp[i-1][j]
    dp[i][j] %= 10**9+7
print(dp[h-1][w-1])

Solution (Python):
from heapq import heappop, heappush

h, w = map(int, input().split())
a = [['

MOD = 10 ** 9 + 7



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 a[i-1][j] == '
            continue
        elif a[i-1][j] == '
            dp[i][j] = dp[i][j-1]
        elif a[i][j-1] == '
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD

print(dp[h][w])

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

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

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

for i in range(H):
    for j in range(W):
        if grid[i][j] != '.':
            continue
        if 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][j - 1] + dp[i - 1][j]) % MOD

print(dp[i][j])

Solution (Python):
import sys
input=sys.stdin.readline
mod=10**9+7
h,w=map(int,input().split())
wall='
MAP=[wall]
for _ in range(h):
    MAP.append('
MAP.append(wall)
DP=[[0]*(w+2) for _ in range(h+2)]
DP[1][1]=1
for i in range(1,h+1):
    for j in range(1,w+1):
        if MAP[i][j]=='.':
            DP[i][j]+=DP[i-1][j]+DP[i][j-1]
            DP[i][j]%=mod
print(DP[h][w])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return


def F():
    s = "abc"*1000
    t = "abc"*1000
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
        
    print(dp[len(s)][len(t)])
    return


def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return


def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return


def I():
    return 
























if __name__ == '__main__':
    H()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()


def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)

def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)

def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])

if __name__ == "__main__":
    H()

Solution (Python):



import sys


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


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

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

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

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

Solution (Python):

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7

def f(h, w, grid):
    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 grid[i][j] == ".":
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
                if dp[i][j] > mod:
                    dp[i][j] -= mod
    return(dp[h][w])

h, w = map(int, input().split()) 
grid = [["
grid = [["
print(f(h, w, grid))

Solution (Python):
n,m=map(int,input().split())
dp=[0]*(n)
for i in range(n):
	s=input()
	dp[i]=[-1]*m
	for j in range(m):
		if s[j]=="
			dp[i][j]=0
fill=1
for i in range(m):
	if dp[0][i]<0:
		dp[0][i]=fill
	else:
		fill=0
fill=1
for i in range(1,n):
	if dp[i][0]<0:
		dp[i][0]=fill
	else:
		fill=0
for i in range(1,n):
	for j in range(1,m):
		if dp[i][j]<0:
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
print(dp[n-1][m-1])

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

Solution (Python):
h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))
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 a[i][j] == '
            dp[i][j] = 0
        else:
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
            dp[i][j] = dp[i][j] % mod
print(dp[-1][-1])

Solution (Python):
H, W = list(map(int, input().split()))
L = []
ansL = [[0 for i in range(W)] for j in range(H)]
ansL[0][0] = 1

for i in range(H):
	L.append(list(input()))

for i in range(W):
	for j in range(H):
		if L[j][i] == ".":
			if i >= 1:
				ansL[j][i] += ansL[j][i - 1]
			if j >= 1:
				ansL[j][i] += ansL[j - 1][i]
			ansL[j][i] = ansL[j][i] % 1000000007

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

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

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

md = 1e9 + 7
dp = [ [0]*W for _ in range(H) ]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if a[h][w] == '.':
            if w > 0:
                dp[h][w] += dp[h][w-1]
            if h > 0:
                dp[h][w] += dp[h-1][w]
        dp[h][w] %= md

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

Solution (Python):
H, W = (int(i) for i in input().split()) 

G = []
for i in range(H):
    G.append(input())


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

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


for hh in range(H):
    for ww in range(W):
        if G[hh][ww] == "
            dp[hh + 1][ww + 1] = 0
        else:
            if hh == 0 and ww == 0:
                dp[0][0] = 1
            else:
                dp[hh + 1][ww + 1] = dp[hh][ww + 1] + dp[hh+1][ww]


print(dp[hh+1][ww+1] % (10 ** 9 + 7))

Solution (Python):


"""
Created on 2019/3/7
Update on 2019/3/
Solved on 2019/3/  
@author: shinjisu
"""









def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]



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



def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  
    mat = zeros((n, m))
    
    for i in range(n):
        mat[i] = getIntList()
    return mat


def zeros2(n, m): return [zeros(m) for i in range(n)] 

ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_H_v1():  
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '
    BLANK = '.'
    dp = zeros((H+1, W+1))
    dp[1, 1] = 1
    dmp(dp, 'dp initial')
    for i in range(H):
        for j in range(W):
            if a[i][j] == BLANK and (i > 0 or j > 0):
                dp[i+1, j+1] = (dp[i, j+1] + dp[i+1, j]) % N1097

    dmp(dp, 'dp')
    return dp[H, W]


def prob_H_v2():  
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '
    BLANK = '.'
    dp = zeros((H+1, W+1))
    dp[1, 1] = 1
    dmp(dp, 'dp initial')
    for i in range(1, H):
        if a[i][0] == BLANK:
            dp[i+1, 1] = dp[i, 1]
    for j in range(1, W):
        if a[0][j] == BLANK:
            dp[1, j+1] = dp[1, j]
    for i in range(1, H):
        for j in range(1, W):
            if a[i][j] == BLANK:
                dp[i+1, j+1] = (dp[i, j+1] + dp[i+1, j]) % N1097

    dmp(dp, 'dp')
    return dp[H, W]




def prob_H():  
    H, W = getIntList()
    dmp((H, W), 'H, W')
    a = []
    for i in range(H):
        a.append(input())
    dmp(a)
    WALL = '
    BLANK = '.'
    dp = zeros2(H+1, W+1)
    dp[0][1] = 1  
    dmp(dp, 'dp initial')
    for i in range(H):
        for j in range(W):
            if a[i][j] == WALL:
                continue
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][ j]) % N1097

    dmp(dp, 'dp')
    return dp[H][ W]


debug = False  
ans = prob_H()
print(ans)

Solution (Python):

def count_paths(A, DP, N, M):
    DP[0][0] = 1
    for i in range(N):
        for j in range(M):
            if i==0 and j==0:
                DP[0][0] = 1
            else:
                if A[i][j] == '
                    DP[i][j] = 0
                else:
                    DP[i][j] = (DP[i-1][j]+DP[i][j-1])%(1000000007)
    return DP[N-1][M-1]
N, M = [int(s) for s in input().split(" ")]
A = []
DP = []
for i in range(N):
    DP.append([0]*M)
    z = [ch for ch in input()]
    A.append(z)
result = count_paths(A, DP, N, M)
print("{}".format(result))

Solution (Python):

"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import math
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

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

FMOD = 1000000007.0
fmod = lambda x: x - FMOD * math.trunc(x / FMOD)

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

grid = [input() + '
grid.append('

dp = [[0.0] * (w + 1) for _ in range(h + 1)]
dp[-2][-2] = 1.0

for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if (i == h - 1) and (j == w - 1):
            continue
        dp[i][j] = fmod((dp[i + 1][j] if grid[i + 1][j] == '.' else 0.0) +
                        (dp[i][j + 1] if grid[i][j + 1] == '.' else 0.0))

print(int(dp[0][0]) % 1000000007)

Solution (Python):
H, W = [int(i) for i in input().split()]
A = [[s for s in input()] for j in range(H)]
p = 10 ** 9 + 7

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

for h in range(H):
    for w in range(W):
        if h + 1 < H and A[h+1][w] == '.':
            DP[h+1][w] += DP[h][w]
            DP[h+1][w] %= p
        if w + 1 < W and A[h][w+1] == '.':
            DP[h][w+1] += DP[h][w]
            DP[h][w+1] %= p

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

Solution (Python):
import collections

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

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

cnt_list = [[float("inf") for x in range(W)] for y in range(H)]
cnt_list[0][0] = 1

q = collections.deque([(0,0)])

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny = y + dy
        nx = x + dx
        
        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue
        if L[ny][nx] == "
            continue
        if cnt_list[ny][nx] < float("inf") :
            cnt_list[ny][nx] += cnt_list[y][x]
        else :
            cnt_list[ny][nx] = cnt_list[y][x]
            q.append((ny,nx))
ans = cnt_list[-1][-1]
if ans < float("inf") :
    ans %= 10**9+7
else :
    ans = 0

print(ans)

Solution (Python):
n,m = map(int,input().split())
map = [[] * m for _ in range(n)]
dp = [[0] * (m+1) for _ in range(n + 1)]

for _ in range(n):
    tmp = input()
    for __ in tmp:
        map[_].append(__)

if map[n-1][m-1] == '
    print(0)

for t1 in range(n)[::-1]:
    if map[t1][m-1] != '
        dp[t1 + 1][m] = 1
    else:
        break

for t1 in range(m)[::-1]:
    if map[n-1][t1] != '
        dp[n][t1 + 1] = 1
    else:
        break

for i in range(1,n+1)[::-1]:
    for j in range(1,m + 1)[::-1]:
        if map[i-1][j-2] != '
            dp[i-1][j-1] = dp[i][j-1] + dp[i-1][j]
        elif map[i -1][j-2] == '
             dp[i-1][j-1] = dp[i-1][j]
        elif  map[i -1][j-2] != '
             dp[i-1][j-1] = dp[i][j-1]
        else:
            dp[i-1][j-1] = 0

print(dp[1][1] % 1000000007)

Solution (Python):


import sys

INF = 10 ** 5
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


h, w = LI()
B = [SI() for _ in range(h)]

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

for i in range(h):
    for j in range(w):
        if B[i][j] == '
            continue
        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())
s=[list(input()) for i in range(h)]
dp=[[0]*w for i in range(h)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        if i+1<h and s[i+1][j]=='.':dp[i+1][j]+=dp[i][j]
        if j+1<w and s[i][j+1]=='.':dp[i][j+1]+=dp[i][j]
print(dp[-1][-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
for i in range(w):
    if a[0][i] == "
        break
    dp[0][i] = 1
for j in range(h):
    if a[j][0] == "
        break
    dp[j][0] = 1

for i in range(1,h):
    for j in range(1,w):
        if a[i][j] == "
            continue
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[h-1][w-1]%(10**9+7))

Solution (Python):
def main(): 
  H, W = list(map(int, input().split()))
  a = []
  for i in range(H):
    a.append(list(input()))
    
  DP = [[0 for i in range(W)] for j in range(H)]
  
  DP[0][0] = 1
  for i in range(1, W):
    if a[0][i] == ".":
      DP[0][i] = 1
    else:
      break
  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[i][j] == ".":
        DP[i][j] = int((DP[i - 1][j] + DP[i][j - 1]) % (1e9 + 7))
  print(DP[-1][-1]) 
main()

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

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

Solution (Python):
h, w = map(int, input().split())
a = [input() for _ in range(h)]

mod = 10**9 + 7

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

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if i + 1 < h and a[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if j + 1 < w and a[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

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

Solution (Python):
H,W = map(int,input().split())
A = [input() for i in range(H)]
MOD = 10**9+7
dp = [[0]*W for i in range(H)]
dp[0][0] = 1

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

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    field = []
    for i in range(H):
        input_raw = read_func().strip().split()
        field.append(input_raw[0])

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

    for i in range(H):
        if field[i][0] == ".":
            dp[i][0] = 1
        else:
            break
    for i in range(W):
        if field[0][i] == ".":
            dp[0][i] = 1
        else:
            break
    for i in range(1, H):
        for j in range(1, W):
            if field[i][j] == ".":
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007L
            else:
                dp[i][j] = 0
    print dp[H - 1][W - 1]

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
H, W = map(int, input().split())
grid = [['

for i in range(H):
    l = input()[:-1]
    for j, c in enumerate(l):
        grid[i+1][j+1] = c

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

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

print(dp[-2][-2])

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


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

fields = []
for _ in xrange(H) : 
    fields.append(list(raw_input().strip()))

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

for r in xrange(H) : 
    if fields[r][0] == '
        break

    dp[r][0] = 1

for c in xrange(W) : 
    if fields[0][c] == '
        break

    dp[0][c] = 1


for r in xrange(1, H) : 
    for c in xrange(1, W) : 
        if fields[r][c] == '
            continue

        dp[r][c] = dp[r - 1][c] + dp[r][c - 1]


print dp[-1][-1] % MOD

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


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

dp[0][0] = 1
if A[0][1] == '.':
    dp[0][1] = 1
if A[1][0] == '.':
    dp[1][0] = 1


for h in range(H):
    for w in range(W):
        if A[h][w] == '.':
            if h * w > 0:
                dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % mod
            elif h == 0 and w == 0:
                pass
            elif h == 0:
                dp[h][w] = dp[h][w-1]
            else:
                dp[h][w] = dp[h-1][w]


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