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):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    h,w = map(int,input().split())
    dp = [[0]*w for i in range(h)]
    a = [input() for i in range(h)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            if i+1 < h and a[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                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])

if __name__ == "__main__":
    main()

Solution (Python):
h,w = list(map(int, input().split()))
mt = [list(input()) for _ in range(h)]
mod = 10**9+7
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1

j = 1
for i in range(1, h+1):
    dp[i][j] = dp[i][j]%mod
    if i < h:
        if mt[i][0] == ".":
            dp[i + 1][1] = dp[i][1]
        else:
            dp[i + 1][1] = 0
    for j in range(1, w):
        if mt[i-1][j] == ".":
            dp[i][j+1] = dp[i][j] + dp[i-1][j+1]
        else:
            dp[i][j+1] = 0

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

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

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

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

Solution (Python):
h, w = list(map(int, input().split()))
field = [[0 for _ in range(w)] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    field[i] = list(input())

dp[0][0] = 1

for i in range(h):
    for j in range(w):
        
        if j + 1 < w and field[i][j+1] != "
            dp[i][j+1] += dp[i][j]
        
        if i + 1 < h and field[i+1][j] != "
            dp[i+1][j] += dp[i][j]

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

Solution (Python):
r,c = [int(i) for i in input().split()]
mat = []
for i in range(r):
  arr = input()
  tmp = []
  for j in range(c):
    if arr[j] == '.':
      tmp.append(-1)
    else:
      tmp.append(-2)
  mat.append(tmp)


mat[r-1][c-1] = 1
for i in range(c-2, -1, -1):
  if mat[r-1][i] == -1:
    mat[r-1][i] = mat[r-1][i+1]
  elif mat[r-1][i] == -2:
    mat[r-1][i] = 0


for j in range(r-2, -1, -1):
  if mat[j][c-1] == -1:
    mat[j][c-1] = mat[j+1][c-1]
  elif mat[j][c-1] == -2:
    mat[j][c-1] = 0


for i in range(r-2, -1, -1):
  for j in range(c-2, -1, -1):
    if mat[i][j] == -2:
      mat[i][j] = 0
    else:
      mat[i][j] = (mat[i+1][j] + mat[i][j+1])%1000000007
print("%s" % mat[0][0])

Solution (Python):
H, W = [int(item) for item in input().split()]
grid = [[item for item in input().strip()] for _ in range(H)]




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

for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            pass
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j])%(10**9+7)

print(dp[H][W])

Solution (Python):
H, W = [int(item) for item in input().split()]
grid = [[item for item in input().strip()] for _ in range(H)]




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

for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            pass
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]

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

Solution (Python):
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

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

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    
    print(dp[H][W])

if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
M = [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 M[i][j] == "
            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])

Solution (Python):



MAX = 10**9 + 7

def main():
  h, w = map(int, input().strip().split())
  dp = [[0]*(w+1) for _ in range(h+1)]
  maze = [input().strip() for _ in range(h)]
  dp[1][0] = 1
  for i in range(1, h+1):
    for j in range(1, w+1):
      if maze[i-1][j-1] == '
        continue
      dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MAX
  print(dp[-1][-1])


if __name__=='__main__':
  main()

Solution (Python):
def main():
  import sys
  import numpy as np
  input=sys.stdin.readline
  h,w=map(int,input().split())
  meize=[list(input()) for i in range(h)]
  mod=10**9+7

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

  dp[0][1]=1
  for i in range(h):
    for j in range(w):
      if meize[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]%=mod

  print(dp[h][w]%mod)
  
if __name__=='__main__':
  main()

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

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

dp[0][1]=1
for i in range(h):
  for j in range(w):
    if meize[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]%=mod

print(dp[h][w]%mod)

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

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

dp[0][1]=1
for i in range(h):
  for j in range(w):
    if meize[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]%=mod

print(dp[h][w]%mod)

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

dp = [[0]*w for i in range(h)]
inf = 10**9+7

dp[0][0] = 1

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

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

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

dp = [[0]*w for i in range(h)]
inf = 10**9+7

dp[0][0] = 1

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

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

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

    mod = 10 ** 9 + 7

    h, w = map(int, readline().split())
    a = [readline().rstrip() for _ in range(h)]

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

    for r in range(h):
        for c in range(w):
            if a[r][c] == '
            if r > 0:
                dp[r][c] += dp[r - 1][c]
            if c > 0:
                dp[r][c] += dp[r][c - 1]
            dp[r][c] %= mod

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


if __name__ == '__main__':
    main()

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

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


for i in range(H):
    for j in range(W):
        if gridlist[i][j] == '
            matrix[i][j] = 0



for i in range(H):
    for j in range(W):
        up = 0
        left = 0
        if matrix[i][j] == 0:
            continue
        if i==0 and j == 0:
            continue
        if i > 0:
            left = matrix[i-1][j]
        if j > 0:
            up = matrix[i][j-1]
        matrix[i][j] = left + up
        

print(matrix[i][j] % (10**9 + 7))

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


dp = []
for i in range(H):
    retsu = []
    for j in range(W):
        if grid[i][j] == '.':
            retsu.append(1)
        else:
            retsu.append(0)
    dp.append(retsu)

for i in range(H):
    for j in range(W):
        if j - 1 >= 0 and i-1>=0:
            if grid[i][j] == '
                continue
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
        elif i - 1 >= 0:
            if grid[i][j] == '
                continue
            dp[i][j] = 0 + dp[i-1][j]
        elif j - 1 >= 0:
            if grid[i][j] == '
                continue
            dp[i][j] = dp[i][j-1] + 0
        else:
            dp[i][j] = 1

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

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

maze = [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 maze[i][j] != '
            if i != 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j] % d) % d
            if j != 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1] % d) % d

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

Solution (Python):
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  dp=[[0]*w for _ in range(h)]
  dp[0][0]=1

  l=[S() for _ in range(h)]

  for i in range(h):
    for j in range(w):
      
      y=i-1
      x=j-1

      if y<0 and x<0:
        continue
      if l[i][j]=='
        continue
      if y<0:
        dp[i][j]=dp[i][j-1]
      elif x<0:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod

  return dp[h-1][w-1]


print(main())

Solution (Python):
h, w = map(int, input().split())
l = [0]*h
for i in range(h):
  l[i] = str(input())
  
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 l[i+1][j] == '.':
      dp[i+1][j] += dp[i][j]
    if j+1 < w and l[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())
l = [0]*h
for i in range(h):
  l[i] = str(input())
  
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 l[i+1][j] == '.':
      dp[i+1][j] += dp[i][j]
    if j+1 < w and l[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())
l=[list(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==j==0:
   continue
  if l[i][j]=='
   dp[i][j]==0
   continue

  if i-1>=0 and l[i-1][j]=='.':
   dp[i][j]+=dp[i-1][j]
  if j-1>=0 and l[i][j-1]=='.':
   dp[i][j]+=dp[i][j-1]

  dp[i][j]%=mod

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

Solution (Python):
h,w=map(int,input().split())
l=[list(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==j==0:
   continue
  if l[i][j]=='
   dp[i][j]==0
   continue

  if i-1>=0 and l[i-1][j]=='.':
   dp[i][j]+=dp[i-1][j]
  if j-1>=0 and l[i][j-1]=='.':
   dp[i][j]+=dp[i][j-1]

  dp[i][j]%=mod

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

Solution (Python):
H,W=map(int,input().split())
temp=[]
mod=(10**9)+7
for r in range(H):
    s=input()
    temp.append(s)
grid=[]
for i in temp:
    x=[]
    for j in i:
        if j==".":
            x.append(0)
        else:
            x.append(1)
    grid.append(x)
dp=[]
for i in range(H):
    x=[-1]*W
    for j in range(W):
        if grid[i][j]==1:
            x[j]=0
    dp.append(x)
dp[H-1][W-1]=1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if grid[i][j]==1 or (i==H-1 and j==W-1):
            continue
        else:
            a=0
            b=0
            if (j+1)<W:
                a=dp[i][j+1]
            if (i+1)<H:
                b=dp[i+1][j]
            dp[i][j]=a+b
print(dp[0][0]%mod)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    a=[[] for _ in range(H+2)]
    a[0]=a[H+1]='
    for i in range(1,H+1):
        a[i]='
    dp=[[0]*(W+2) for _ in range(H+2)]
    for column in range(1,H+1):
        for row in range(1,W+1):
            if column==row==1:
                dp[column][row]=1
            elif a[column][row]=='.':
                dp[column][row]=(dp[column-1][row]+dp[column][row-1])%MOD
    print(dp[H][W])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    a=[[] for _ in range(H+2)]
    a[0]=a[H+1]='
    for i in range(1,H+1):
        a[i]='
    dp=[[0]*(W+2) for _ in range(H+2)]
    dp[1][1]=1
    que=deque()
    que.append((1,1))
    dx=[1,0]
    dy=[0,1]
    used=[[False]*(W*2) for _ in range(H+2)]
    used[1][1]=True
    while que:
        y,x=que.popleft()
        for k in range(2):
            ny,nx=y+dy[k],x+dx[k]
            if a[ny][nx]=='.':
                dp[ny][nx]+=dp[y][x]
                dp[ny][nx]%=MOD
                if not used[ny][nx]:
                    que.append((ny,nx))
                    used[ny][nx]=True
    print(dp[H][W])

if __name__ == '__main__':
    main()

Solution (Python):
H,W = map(int,input().split())
mod = 10**9+7
M = []
for i in range(H):
    M.append(input())
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 != H-1 and M[i+1][j] == '.':
            dp[i+1][j] += dp[i][j] % mod
        if j != W-1 and M[i][j+1] == '.':
            dp[i][j+1] += dp[i][j] % mod
print(dp[-1][-1]%mod)

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


a = [[-1] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        if s[j-1] == ".":
            a[i][j] = 0
        elif s[j-1] == "
            a[i][j] = -1
        else:
            print("ERROR")


dp_sum = [[0] * (W+2) for i in range(H+2)]

steplst =  [[] for i in range((H+W)+2)]

stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    if n == 1:
        x,y = 1,1
        a[x][y] = -9
        for dx,dy in stepdxy:
            if a[x+dx][y+dy] == 0 or a[x+dx][y+dy] == n:
                dp_sum[x+dx][y+dy] += 1
                a[x+dx][y+dy] = n
                steplst[n].append([x+dx,y+dy])
                stepok = 1
    else:
        for x,y in steplst[n-1]:
            for dx,dy in stepdxy:
                if a[x+dx][y+dy] == 0:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
                    a[x+dx][y+dy] = n
                    steplst[n].append([x+dx,y+dy])
                    stepok = 1
                elif a[x+dx][y+dy] == n:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
    return stepok

stepn = 1
while do_step(stepn) == 1:
    
    
    stepn += 1

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

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


a = [[-1] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        if s[j-1] == ".":
            a[i][j] = 0
        elif s[j-1] == "
            a[i][j] = -1
        else:
            print("ERROR")


dp_sum = [[0] * (W+2) for i in range(H+2)]

stepdic = {}

stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    if n == 1:
        x,y = 1,1
        a[x][y] = -9
        for dx,dy in stepdxy:
            if a[x+dx][y+dy] == 0 or a[x+dx][y+dy] == n:
                dp_sum[x+dx][y+dy] += 1
                a[x+dx][y+dy] = n
                stepdic.setdefault(n,[]).append([x+dx,y+dy])
                stepok = 1
    if n-1 in stepdic.keys():
        for x,y in stepdic[n-1]:
            for dx,dy in stepdxy:
                if a[x+dx][y+dy] == 0:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
                    a[x+dx][y+dy] = n
                    stepdic.setdefault(n,[]).append([x+dx,y+dy])
                    stepok = 1
                elif a[x+dx][y+dy] == n:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
    return stepok

stepn = 1
while do_step(stepn) == 1:
    stepn += 1

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

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

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

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

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

al = []

MOD = 10**9 + 7
for _ in range(h):
   a = list(input())
   al.append(a)

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+1 < h and al[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
        if j+1 < w and al[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
            
print(dp[-1][-1])

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    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:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() 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]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examH()

"""

"""

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    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:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() 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]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examH()

"""

"""

Solution (Python):
from collections import deque
H,W = map(int,input().split())
Grid = [list(input()) for _ in range(H)]
lis = [[0]*W for _ in range(H)]
lis[0][0] = 1
M = 10**9+7

for i in range(H):
    for j in range(W):
        if i != H-1 and Grid[i+1][j] == ".":
            lis[i+1][j] += lis[i][j]%M
        if j != W-1 and Grid[i][j+1] == ".":
            lis[i][j+1] += lis[i][j]%M

print(lis[H-1][W-1] % M)

Solution (Python):
h,w=map(int,input().split())
mod=10**9+7
W0=[list('
Wh=[list('
HW=W0+[list('

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





h,w = mii()
mat = llstr(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 and j==0:
            continue
        if i==0 and mat[i][j]==".":
            dp[i][j] = dp[i][j-1]
        elif i>0 and mat[i][j]==".":
            if mat[i-1][j]=="
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] =dp[i][j-1]+dp[i-1][j]
    
print(dp[-1][-1]%(mod))

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

MOD = 10 ** 9 + 7


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

for i in range(h):
  for j in range(w):
    if (i + 1 < h and A[i+1][j] == "."):
      dp[i+1][j] += dp[i][j] 
    if (j + 1 < w and A[i][j+1] == "."):
      dp[i][j+1] += dp[i][j] 
ans = dp[h-1][w-1] % MOD
print(ans)

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

M[0][0] = 1
for h in range(H):
  for w in range(W):
    if M[h][w] == ".":
      M[h][w] = ((M[h-1][w] if h-1 >= 0 and M[h-1][w] != "
print(M[-1][-1])

Solution (Python):
import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid = grid.tolist()

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

cost[1][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        c = cost[i][j]
        if grid[i+1][j]:
            cost[i+1][j] += c
            cost[i+1][j] %= mod
        if grid[i][j+1]:
            cost[i][j+1] += c
            cost[i][j+1] %= mod

ans = cost[H][W]
print(ans)

Solution (Python):
MOD = 10**9+7
h,w = map(int,input().split())
grid = [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 grid[i][j]=='
      continue
    if i>0:
      dp[i][j] += dp[i-1][j]
    if j>0:
      dp[i][j] += dp[i][j-1] 

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