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

R, C = map(int, input().split())
maze =["
visited = [[0]*(C+2) for j in range(R+2)]
INF=10**9+7
for i in range(1,R+1):
    for j in range(1,C+1):
        if i==1 and j==1:visited[1][1]=1
        elif maze[i][j]==".":
            visited[i][j]=(visited[i-1][j]+visited[i][j-1])%INF
            if i==R and j==C:print(visited[i][j])

Solution (Python):
h,w =list(map(int,input().split()))
mod=10**9+7
a = [[i for i in input()] for j 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 and j==0: pass
		elif a[i][j]!="
			if i==0 : dp[i][j]=dp[i][j-1]
			elif j==0: dp[i][j]=dp[i-1][j]
			else:dp[i][j]=dp[i-1][j]+dp[i][j-1]
		else: dp[i][j]=0
		dp[i][j]=dp[i][j]%mod
print(dp[h-1][w-1])

Solution (Python):
h,w =list(map(int,input().split()))
mod=10**9+7
a = [[i for i in input()] for j 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 and j==0: pass
		elif a[i][j]!="
			if i==0 : dp[i][j]=dp[i][j-1]
			elif j==0: dp[i][j]=dp[i-1][j]
			else:dp[i][j]=dp[i-1][j]+dp[i][j-1]
		else: dp[i][j]=0
		dp[i][j]=dp[i][j]%mod
print(dp[h-1][w-1])

Solution (Python):







from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii(): return int(input())
def si(): return input()
def mi(): return map(int,input().strip().split(" "))
def li(): return list(mi())

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()
    







abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007

inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[0] 
def sort2(l):return sorted(l, key=getKey)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():



    

    n,m=mi()
    s=[]
    cache=d2(1005,1005,0)
    for i in range(n):
        s.append(list(si()))

    if s[0][0]=='
        print(0)
        exit()

    cache[1][1]=1






    for i in range(2,m+1):
        if s[0][i-1]=='.':
            cache[1][i]=cache[1][i-1]

    for i in range(2,n+1):
        if s[i-1][0]=='.':
            cache[i][1]=cache[i-1][1]


    for i in range(1,n+1):
        for j in range(1,m+1):

            if i!=1 and j!=1:
    
                if s[i-1][j-1]=='
                    cache[i][j]=0
                    continue
        
                if s[i-1][j-2]=='.':
                    cache[i][j]+=cache[i][j-1]

                if s[i-2][j-1]=='.':
                    cache[i][j]+=cache[i-1][j]


    print(cache[n][m]%mod)
    
    












    









BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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




if __name__ == "__main__":
    
    main()

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

    dp = [[0 for j in range(w)] for i in range(h)]
    for j in range(w):
        if grid[0][j] == '.':
            dp[0][j] = 1
        else:
            break

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

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

            dp[i][j] %= mod

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

main()

Solution (Python):
h,w=map(int, input().split())
s=[list(input()) for i in range(h)]
dp=[[0]*(w+2) for i in range(h+2)]
dp[0][1]=1

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
        else:
            pass
    
        
print(dp[h][w]%(10**9+7))

Solution (Python):
h, w = [ int(v) for v in input().split() ]

mod = 10**9+7
ans_list = [ 0 for i in range(w) ]
ans_list[0] = 1


line = input()
for i in range(1,w):
    if line[i] == ".":
        ans_list[i] = ans_list[i-1]
    else:
        ans_list[i] = 0


for j in range(1,h):
    new_ans_list = [ 0 for i in range(w) ]
    line = input()
    if line[0] == ".":
        new_ans_list[0] = ans_list[0] 
    else:
        new_ans_list[i] = 0

    for i in range(1,w):
        if line[i] == ".":
            new_ans_list[i] = (new_ans_list[i-1] + ans_list[i]) % mod
        else:
            new_ans_list[i] = 0

    ans_list = new_ans_list

print(ans_list[-1])

Solution (Python):
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(read_line(n=w))
    return a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    wall_symbol = '

    h = len(a)
    w = len(a[0])

    ways_count_to_get = [[0 for x in range(w)] for y in range(h)]
    ways_count_to_get[0][0] = 1

    for y in range(h):
        for x in range(w):
            if x == 0 and y == 0:
                continue
            if x == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y - 1][x]
                    continue
            if y == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y][x - 1]
                    continue
            if a[y][x] == wall_symbol:
                ways_count_to_get[y][x] = 0
            else:
                ways_count_to_get[y][x] = (ways_count_to_get[y - 1][x] + ways_count_to_get[y][x - 1]) % mode

    return ways_count_to_get[h - 1][w - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    h, w = read_int(2)
    a = []
    for y in range(h):
        a.append(read_line(n=w))
    return a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    wall_symbol = '

    h = len(a)
    w = len(a[0])

    ways_count_to_get = [[0 for x in range(w)] for y in range(h)]
    ways_count_to_get[0][0] = 1

    for y in range(h):
        for x in range(w):
            if x == 0 and y == 0:
                continue
            if x == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y - 1][x]
                    continue
            if y == 0:
                if a[y][x] == wall_symbol:
                    continue
                else:
                    ways_count_to_get[y][x] = ways_count_to_get[y][x - 1]
                    continue
            if a[y][x] == wall_symbol:
                ways_count_to_get[y][x] = 0
            else:
                ways_count_to_get[y][x] = (ways_count_to_get[y - 1][x] + ways_count_to_get[y][x - 1]) % mode

    return ways_count_to_get[h - 1][w - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(1000 * 1000)
    solve()

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

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

for i in range(H):
    maze[i] = list(str(input()))

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

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

Solution (Python):
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
Ms = [input().strip("\n") for _ in range(H)]

C = 10 ** 9 + 7
dp = [0] * (W + 1)
dp[0] = 1
for row in Ms:
    for i in range(len(row)):
        i1 = i + 1
        if row[i] == '
            dp[i1] = 0
        else:
            dp[i1] += dp[i]
            dp[i1] %= C
    dp[0] = 0
print(dp[W])

Solution (Python):
h,w=map(int,input().split())
a=[]
dp=[[] for i in range(h)]
for i in range(h):
  for j in range(w):
    dp[i].append(0)
for i in range(h):
  b=input()
  a.append(b)
for i in range(h):
  if a[i][0]=="
    break
  dp[i][0]=1
for i in range(w):
  if a[0][i]=="
    break
  dp[0][i]=1
for i in range(1,h):
  for j in range(1,w):
    if a[i][j]=="
      continue
    else:
      dp[i][j]=dp[i-1][j]+dp[i][j-1]
ans=dp[h-1][w-1]
while(ans>1000000007):
  ans=ans%1000000007
print(ans)

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

a = [input().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] == '.':
            for rp, cp in ((r - 1, c), (r, c - 1)):
                if not (rp < 0 or cp < 0):
                    dp[r][c] += dp[rp][cp]
print(dp[-1][-1] % (10 ** 9 + 7))

Solution (Python):
import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)

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

Solution (Python):



import sys
sys.setrecursionlimit(10000000)
def LI(): return list(map(int,sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
mod = 10**9+7

def h():
    h,w = LI()
    grid = [list(input()) for _ in range(h)]

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [sys.stdin.readline()[:-1] for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

H, W = LI()
a = LSR(H)


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

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [sys.stdin.readline()[:-1] for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

H, W = LI()
a = LSR(H)


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

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

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['

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

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])

Solution (Python):
import sys
H,W=list(map(int,input().strip().split(' ')))
grid=[]
for _ in range(H):
    grid+=[input()]
dp=[[0]*W for i in range(H)]
dp[0][0]=1
MOD=10**9+7
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        if grid[i][j]=="
            continue
        temp1=0
        temp2=0
        if i>0:
            temp1=dp[i-1][j]
        if j>0:
            temp2=dp[i][j-1]
        dp[i][j]=(temp1+temp2)%(MOD)
print(dp[-1][-1])

Solution (Python):
from __future__ import division, print_function
def main():
    n,m=map(int,input().split())
    l1=[]
    for i in range(n):
        l1.append(input())
    dp=[ [0]*m for _ in range(n)]
    dp[0][0]=1
    mod=10**9+7
    for i in range(n):
        for j in range(m):
            if l1[i][j]=='
                continue
            if i>0:
                if l1[i-1][j]=='.':
                    dp[i][j]=(dp[i][j]+dp[i-1][j])%mod
            if j>0:
                if l1[i][j-1]=='.':
                    dp[i][j]=(dp[i][j]+dp[i][j-1])%mod
    print(dp[n-1][m-1])











py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


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


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

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














for hindex in range(h):
    for windex in range(w):
        if hindex == windex == 0:
            dp[hindex][windex] = 1
        elif field[hindex][windex] == "
            dp[hindex][windex] = 0
        else:
            dp[hindex][windex] = (hindex and dp[hindex - 1][windex]) + (windex and dp[hindex][windex - 1])
print(dp[hindex][windex] % (10**9 + 7))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

dp = [[None] * w for _ in range(h)]
def dfs(hindex=h - 1, windex=w - 1):
    if field[hindex][windex] == "
        return 0
    if hindex == windex == 0:
        return 1

    if dp[hindex][windex] is not None:
        return dp[hindex][windex]
    r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
    dp[hindex][windex] = r
    return r

print(dfs() % (10**9 + 7))

Solution (Python):


import sys

class HGrid1:
    def solve(self):
        MOD = 10 ** 9 + 7
        h, w = [int(_) for _ in input().split()]
        a = []
        for i in range(h):
            a.append(list(input()))

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

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

solver = HGrid1()
input = sys.stdin.readline

solver.solve()

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

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

dp = []
for _ in range(H):
    row = [0] * W
    dp.append(row)
   
P = 1000000007
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
            
        if GRID[i][j] == '
            continue

        v = 0
        
        if i-1 >= 0:
            v = (v + dp[i-1][j]) % P
        
        if j-1 >= 0:
            v = (v + dp[i][j-1]) % P

        dp[i][j] = v


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 for _ in range(w+1)] for _ in range(h+1)]
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):
import sys
input = sys.stdin.readline

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

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
 
for y in range(H):
  for x in range(W):
    if y+1 < H and A[y+1][x] == '.':
      dp[y+1][x] += dp[y][x]
      dp[y+1][x] = dp[y+1][x] % MOD

    if x+1 < W and A[y][x+1] == '.':
      dp[y][x+1] += dp[y][x]
      dp[y][x+1] = dp[y][x+1] % MOD

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

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

mod = 10 ** 9 + 7
H, W = map(int, input().split())
field = []
dp = [[0] * W for _ in range(H)]

for _ in range(H):
	field.append(input())

dp[0][0] = 1

for i in range(H):
	for j in range(W):
		if field[i][j] == '.':
			if i > 0:
				dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod
			if j > 0:
				dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod
				
print(dp[-1][-1])

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

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

for y in range(1,H+1):
    for x in range(1,W+1):
        if A[y][x] == '
            dp[y][x] = 0
        else:
            dp[y][x] = dp[y-1][x] + dp[y][x-1]
            dp[y][x] %= MOD

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

Solution (Python):
from collections import deque
DVSR = 1000000007
def LI(): return [int(x) for x in input().split()]
H,W=LI()
MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and nx < W and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)

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

Solution (Python):
from collections import deque
DVSR = 1000000007
def LI(): return [int(x) for x in input().split()]
H,W=LI()
MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and ny >= 0 and nx < W and nx >= 0 and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)

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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

H,W=LI()

MP=[input() for _ in range(H)]
MEMO=[[(-1,0)]*W for _ in range(H)]
MEMO[0][0] = (0,1)
QU=deque([])

QU.append((0,0,0))
IT=[(1,0),(0,1)]
while QU:
    i,j,cost = QU.popleft()
    cost+=1
    pat = MEMO[i][j][1]
    for dy, dx in IT:
        ny, nx = i+dy, j+dx
        if ny < H and ny >= 0 and nx < W and nx >= 0 and MP[ny][nx] == '.':
            cost2, pat2 = MEMO[ny][nx]
            if cost2 == -1:
                
                MEMO[ny][nx] = (cost, pat)
                QU.append((ny,nx,cost))
            elif cost2 == cost:
                _pat = (pat+pat2)%DVSR
                MEMO[ny][nx] = (cost,_pat)
                
                

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

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


print(dp[r][c]%mod)