Educational DP Contest - Grid 1

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}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}


Output

Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Examples

Input

3 4
...#
.#..
....


Output

3


Input

5 2
..
.
..
.#
..


Output

0


Input

5 5
..#..
.....
...#
.....
..#..


Output

24


Input

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................


Output

345263555

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(H, W) = map(int, input().split())
l = [[0 if i == '.' else 1 for i in input()] for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 1000000007
for i in range(H):
	for j in range(W):
		if l[i][j]:
			continue
		if i > 0:
			dp[i][j] += dp[i - 1][j] % mod
		if j > 0:
			dp[i][j] += dp[i][j - 1] % mod
print(dp[H - 1][W - 1] % mod)


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


(H, W) = map(int, input().split(' '))
a = []
for i in range(H):
	ai = input()
	a.append(ai)
md = 1000000000.0 + 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]))


(h, w) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * (w + 1) for i in range(h + 1)]
dp[1][0] = 1
for i in range(1, h + 1):
	line = input()
	for j in range(1, w + 1):
		if line[j - 1] != '#':
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
print(dp[-1][-1] % mod)


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


(R, C) = map(int, input().split())
arr = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
dp[1][1] = 1
for i in range(1, R + 1):
	for j in range(1, C + 1):
		if arr[i - 1][j - 1] == '#':
			dp[i][j] = 0
		else:
			dp[i][j] = max(dp[i][j], dp[i - 1][j] + dp[i][j - 1]) % 1000000007
print(dp[-1][-1])


(h, w) = map(int, input().split())
mat = []
dp = []
m = 10 ** 9 + 7
for i in range(h):
	mat.append(list(input()))
	dp.append(list([0] * w))
dp[0][0] = 1
for x in range(h):
	for y in range(w):
		if x != 0 or y != 0:
			if mat[x][y] == '#':
				dp[x][y] = 0
			else:
				dp[x][y] = (dp[x - 1][y] + dp[x][y - 1]) % m
print(dp[h - 1][w - 1])


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


(h, w) = map(int, input().split())
a = []
mod = 10 ** 9 + 7
h += 2
w += 2
a.append('#' * w)
for i in range(h - 2):
	a.append('#' + input() + '#')
a.append('#' * w)
dp = [[0 for i in range(w)] for j in range(h)]
dp[0][1] = 1
for i in range(1, h - 1):
	for j in range(1, w - 1):
		if a[i][j] == '.':
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[h - 2][w - 2])


(h, w) = map(int, input().split())
p = 10 ** 9 + 7
S = [input() for i in range(h)]
DP = [[0 for j in range(w)] for i in range(h)]
DP[0][0] = 1
for i in range(h):
	for j in range(w):
		if i > 0 and S[i - 1][j] == '.':
			DP[i][j] += DP[i - 1][j]
		if j > 0 and S[i][j - 1] == '.':
			DP[i][j] += DP[i][j - 1]
		DP[i][j] %= p
print(DP[h - 1][w - 1])


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


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
count = [0] * W
row = input()
for w in range(W):
	if row[w] == '#':
		break
	else:
		count[w] = 1
for h in range(1, H):
	row = input()
	if row[0] == '#':
		count[0] = 0
	for w in range(1, W):
		if row[w] == '#':
			count[w] = 0
		else:
			count[w] = (count[w - 1] + count[w]) % MOD
print(count[-1])


(H, W) = map(int, input().split())
c = ['#' * (W + 1)] + ['#' + input() + '#' for _ in range(H)] + ['#' * (W + 1)]
mod = 10 ** 9 + 7
dp = [[0] * (W + 2) for _ in range(H + 2)]
dp[1][1] = 1
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
for h in range(1, H + 1):
	for w in range(1, W + 1):
		for (x, y) in direction:
			if c[h + x][w + y] == '.':
				dp[h + x][w + y] = (dp[h + x][w + y] + dp[h][w]) % mod
print(dp[H][W])


(H, W) = map(int, input().split())
S = [input() for i in range(H)]
MOD = 10 ** 9 + 7
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[1][0] = 1
for i in range(H):
	s = S[i]
	for j in range(W):
		if s[j] == '#':
			continue
		dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MOD
print(dp[H][W])


(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for w in range(1, W):
	if a[0][w] != '#':
		dp[0][w] = dp[0][w - 1]
for h in range(1, H):
	if a[h][0] != '#':
		dp[h][0] = dp[h - 1][0]
	for w in range(1, W):
		if a[h][w] != '#':
			dp[h][w] = (dp[h][w - 1] + dp[h - 1][w]) % 1000000007
print(dp[H - 1][W - 1])


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


(h, w) = list(map(int, input().split()))
m = 1000000007
grid = [input() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] = 1
for y in range(h):
	for x in range(w):
		if grid[y][x] == '.':
			if y > 0:
				dp[y][x] += dp[y - 1][x]
			if x > 0:
				dp[y][x] += dp[y][x - 1]
			dp[y][x] %= m
print(dp[h - 1][w - 1])


(H, W) = map(int, input().split())
G = [list(str(input())) for _ in range(H)]
P = 10 ** 9 + 7
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 G[i - 1][j - 1] == '#':
			DP[i][j] = 0
		else:
			DP[i][j] += DP[i - 1][j] + DP[i][j - 1]
			DP[i][j] = DP[i][j] % P
print(DP[H][W])


(H, W) = map(int, input().split())
L = []
for i in range(H):
	l = input()
	L.append(l)
dp = [[0] * (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 L[i - 1][j - 1] == '.':
			dp[i][j] = dp[i][j] + dp[i][j - 1] + dp[i - 1][j]
print(dp[-1][-1] % (10 ** 9 + 7))


(n, m) = map(int, input().split())
s = []
dp = []
mod = 10 ** 9 + 7
for _ in range(n):
	s.append(input())
	dp.append([0] * m)
for i in range(n):
	for j in range(m):
		if i == 0 and j == 0:
			dp[i][j] = 1
		elif s[i][j] == '#':
			dp[i][j] = 0
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[n - 1][m - 1])


(h, w) = map(int, input().split())
maze = [tuple(input()) for _ in range(h)]
dp = [[0] * w for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for y in range(h):
	for x in range(w):
		if maze[y][x] == '#':
			dp[y][x] = 0
		else:
			if y > 0:
				dp[y][x] += dp[y - 1][x]
			if x > 0:
				dp[y][x] += dp[y][x - 1]
			dp[y][x] %= mod
print(dp[-1][-1])


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
mod = int(1000000000.0 + 7)
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
for i in range(1, h + 1):
	dp[i][0] = int(dp[i - 1][0] == 1) * int(a[i - 1][0] == '.')
	for j in range(1, w):
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) * int(not a[i - 1][j] == '#') % mod
print(dp[-1][-1])


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


(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(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]
		dp[i][j] %= MOD
print(dp[-1][-1])


(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] == '#':
		break
	dp[i][0] = 1
for j in range(W):
	if grid[0][j] == '#':
		break
	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])


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


p = 10 ** 9 + 7
(h, w) = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
	maze[i] = input()
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 maze[i - 1][j - 1] == '.':
			dp[i][j] += dp[i - 1][j] % p + dp[i][j - 1] % p
ans = dp[h][w] % p
print(ans)


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
grid = []
for h in range(H):
	grid.append(list(input()))
dp = [[0] * (W + 1) for h in range(H + 1)]
dp[0][1] = 1
for h in range(1, H + 1):
	for w in range(1, W + 1):
		if grid[h - 1][w - 1] == '#':
			continue
		dp[h][w] = (dp[h][w - 1] + dp[h - 1][w]) % MOD
print(dp[H][W])


import sys
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7
(m, n) = map(int, input().split())
grid = [list(input()) for _ in range(m)]
cache = {}

def dp(i, j):
	if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == '#'):
		return 0
	elif (i, j) in cache:
		return cache[i, j]
	elif i == m - 1 and j == n - 1:
		return 1
	cache[i, j] = dp(i + 1, j) + dp(i, j + 1)
	return cache[i, j]
print(dp(0, 0) % mod)


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


(H, W) = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
for y in range(H):
	for x in range(W):
		if y + 1 < H and STAGE[y + 1][x] == '.':
			dp[y + 1][x] += dp[y][x] % MOD
		if x + 1 < W and STAGE[y][x + 1] == '.':
			dp[y][x + 1] += dp[y][x] % MOD
print(dp[-1][-1] % MOD)


(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
MOD = 10 ** 9 + 7
dp = [[0] * (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] == '#':
			dp[i + 1][j + 1] = 0
		else:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
print(dp[-1][-1] % MOD)


mod = int(1000000000.0 + 7)
(h, w) = map(int, input().split())
MAP = ['#' * w] + ['#' + input() for _ in range(h)]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][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]) % mod
print(dp[h][w])


(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
mod = 10 ** 9 + 7
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[1][1] = 1
for x in range(1, W + 1):
	for y in range(1, H + 1):
		if x == y == 1:
			continue
		elif A[y - 1][x - 1] != '#' and (dp[y - 1][x] > 0 or dp[y][x - 1] > 0):
			dp[y][x] = dp[y - 1][x] + dp[y][x - 1]
print(dp[H][W] % mod)


(h, w) = map(int, input().split())
arr = [list(map(str, input().rstrip())) for _ in range(h)]
MOD = 10 ** 9 + 7
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 arr[i - 1][j - 1] == '#':
			continue
		else:
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
print(dp[h][w] % MOD)


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


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


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


(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
mod = 10 ** 9 + 7
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 == j == 1:
			dp[i][j] = 1
		elif maze[i - 1][j - 1] == '.':
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[h][w])


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


(H, W) = map(int, input().split())
G = []
mod = 10 ** 9 + 7
for _ in range(H):
	G.extend([1 if a == '#' else 0 for a in input().strip()])
dp = [0] * (H * W)
for i in range(W):
	if G[i]:
		break
	dp[i] = 1
for i in range(W, H * W):
	if not G[i]:
		if i % W:
			dp[i] = (dp[i - 1] + dp[i - W]) % mod
		else:
			dp[i] = dp[i - W]
print(dp[-1])


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


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


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


(n, m) = map(int, input().split())
grid = []
for i in range(n):
	x = list(input())
	grid.append(x)
dp = [[0 for i in range(m)] for j in range(n)]
dp[0][0] = 1
for i in range(n):
	for j in range(m):
		if grid[i][j] != '#':
			if i > 0:
				dp[i][j] += dp[i - 1][j]
			if j > 0:
				dp[i][j] += dp[i][j - 1]
print(dp[n - 1][m - 1] % (10 ** 9 + 7))


(h, w) = map(int, input().split())
A = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
for y in range(h):
	for x in range(w):
		if y < h - 1 and A[y + 1][x] == '.':
			dp[y + 1][x] += dp[y][x]
			dp[y + 1][x] %= MOD
		if x < w - 1 and A[y][x + 1] == '.':
			dp[y][x + 1] += dp[y][x]
			dp[y][x + 1] %= MOD
print(dp[h - 1][w - 1])


(h, w) = map(int, input().split())
A = [list(input()) for i in range(h)]
mod = 10 ** 9 + 7
dp = [[0] * w for i in range(h)]
dp[0][0] = 1
for y in range(h):
	for x in range(w):
		if A[y][x] == '#':
			continue
		if y != 0:
			dp[y][x] += dp[y - 1][x]
		if x != 0:
			dp[y][x] += dp[y][x - 1]
		dp[y][x] %= mod
print(dp[-1][-1])


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


(R, C) = map(int, input().split())
maze = ['#' * (C + 2)] + ['#' + input() + '#' for i in range(R)] + ['#' * (C + 2)]
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])


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


divisor = 10 ** 9 + 7
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if i + 1 < h and a[i + 1][j] != '#':
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % divisor
		if j + 1 < w and a[i][j + 1] != '#':
			dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % divisor
print(dp[h - 1][w - 1])


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


(H, W) = map(int, input().split())
grid = [input() for i in range(H)]
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
m = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		if grid[i][j] == '#':
			continue
		if i >= 1:
			dp[i][j] += dp[i - 1][j]
		if j >= 1:
			dp[i][j] += dp[i][j - 1]
		dp[i][j] %= m
print(dp[-1][-1])


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


import sys

def input():
	return sys.stdin.readline().rstrip()
(H, W) = map(int, input().split())
a = [list(input()) for i in range(H)]
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][1] = 1
mod = 10 ** 9 + 7
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if a[i - 1][j - 1] == '.':
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
			dp[i][j] %= mod
ans = dp[H][W]
print(ans)


from itertools import *
import sys
md = 10 ** 9 + 7
mis = map(int, sys.stdin.readline().split())
(h, w) = mis
t = [[0] * (w + 1) for _ in range(h + 1)]
s = []
for _ in range(h):
	s += [input()]
for (i, j) in product(range(h), range(w)):
	if i == 0 and j == 0:
		t[i + 1][j + 1] = 1
	elif s[i][j] == '.':
		t[i + 1][j + 1] = (t[i][j + 1] + t[i + 1][j]) % md
	else:
		t[i + 1][j + 1] = 0
print(t[-1][-1])


mod = 1000000007
(n, m) = map(int, input().split())
ll = []
dp = []
for i in range(n):
	s = input()
	ll.append(s)
	l = [0] * m
	dp.append(l)
for i in range(n):
	if ll[i][0] == '#':
		break
	dp[i][0] = 1
for j in range(m):
	if ll[0][j] == '#':
		break
	dp[0][j] = 1
for i in range(1, n):
	for j in range(1, m):
		if ll[i][j] != '#':
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[n - 1][m - 1])


MOD = 1000000007
(h, w) = map(int, input().split())
mp = [input() for _ in range(h)]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[1][1] = 1
for y in range(1, h + 1):
	for x in range(1, w + 1):
		if mp[y - 1][x - 1] == '#':
			continue
		dp[y][x] += dp[y - 1][x] + dp[y][x - 1]
		dp[y][x] %= MOD
print(dp[h][w])


(h, w) = map(int, input().split())
lst = []
for _ in range(h):
	lst.append(list(input()))
MOD = 10 ** 9 + 7
dp = [[0] * (w + 1) for _ 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
		elif lst[i - 1][j - 1] == '.':
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
print(dp[h][w])


(H, W) = map(int, input().split())
MOD = 10 ** 9 + 7
A = ['#' * (W + 1)]
for _ in range(H):
	A.append('#' + input())
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])


(h, w) = map(int, input().split())
mat = []
dp = []
dp.append([0] * (w + 1))
for i in range(h):
	l = input()
	mat.append(l)
	dp.append([0] * (w + 1))
dp[0][1] = 1
for i in range(h):
	for j in range(w):
		if mat[i][j] == '.':
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % 1000000007
print(dp[h][w])


(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W + 1)] for __ in range(H + 1)]
dp[1][0] = 1
mod_numb = 1000000007
for h in range(1, H + 1):
	for w in range(1, W + 1):
		if a[h - 1][w - 1] == '#':
			continue
		else:
			dp[h][w] = (dp[h - 1][w] + dp[h][w - 1]) % mod_numb
print(dp[H][W])


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


(N, M) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [0] * ((N + 1) * (M + 1))
dp[1] = 1
for i in range(1, N + 1):
	s = input().strip()
	for j in range(1, M + 1):
		if s[j - 1] == '.':
			dp[i * (M + 1) + j] = (dp[(i - 1) * (M + 1) + j] + dp[i * (M + 1) + j - 1]) % mod
print(dp[N * (M + 1) + M])


(H, W) = [int(v) for v in input().split()]
area = [input() for _ in range(H)]
dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
dp[1][1] = 1
for (h, row) in enumerate(area, 1):
	for (w, cell) in enumerate(row, 1):
		if cell != '#':
			dp[h][w] += int((dp[h - 1][w] + dp[h][w - 1]) % (1000000000.0 + 7))
print(dp[-1][-1])


(H, W) = map(int, input().split())
A = [input() for i in range(H)]
d = [[0] * (W + 1) for i in range(H + 1)]
d[0][1] = 1
m = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		if A[i][j] == '.':
			d[i + 1][j + 1] = (d[i][j + 1] + d[i + 1][j]) % m
print(d[-1][-1])


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


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


(n, m) = map(int, input().split())
a = [0] * n
dp = [[0 for i in range(m)] for j in range(n)]
dp[0][0] = 1
MOD = int(1000000000.0 + 7)
for i in range(n):
	a[i] = input()
for i in range(n):
	for j in range(m):
		if a[i][j] == '.':
			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[n - 1][m - 1])


import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
mod = 10 ** 9 + 7
A = [list(input()[:-1]) for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for h in range(H):
	for w in range(W):
		if h + 1 < H and A[h][w] == '.':
			dp[h + 1][w] += dp[h][w]
		if w + 1 < W and A[h][w] == '.':
			dp[h][w + 1] += dp[h][w]
print(dp[H - 1][W - 1] % mod)


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


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


(h, w) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
dp = [[0] * w] * h
p = 10 ** 9 + 7
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			dp[i][j] = 0
		elif 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 - 1][j] + dp[i][j - 1]) % p
print(dp[h - 1][w - 1])


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


(H, W) = map(int, input().strip().split())
grid = [list(input()) for i in range(H)]
dp = [[0 for i in range(W + 1)] for i in range(H + 1)]
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		if grid[i][j] == '.':
			dp[i + 1][j] += dp[i][j]
			dp[i][j + 1] += dp[i][j]
		dp[i][j] = dp[i][j] % 1000000007
print(dp[H - 1][W - 1])


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)


(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] != '#' else 0) + (M[h][w - 1] if w - 1 >= 0 and M[h][w - 1] != '#' else 0)) % p
print(M[-1][-1])


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


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


(H, W) = map(int, input().split())
a = [input() for i in range(H)]
DP = [[0 for i in range(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 a[i][j] == '.':
			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[-1][-1])


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


(H, W) = map(int, input().split())
p = 10 ** 9 + 7
ma = []
dp = [[0] * (W + 2) for j in range(H + 2)]
an = []
dp[1][1] = 1
for i in range(H):
	ma.append(list(input()))
	for j in range(W):
		if i == j == 0:
			continue
		if ma[i][j] == '#':
			dp[i + 1][j + 1] = 0
		else:
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % p
print(dp[H][W])


(H, W) = map(int, input().split())
a = []
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
for i in range(H):
	a.append(list(input()))
for i in range(H):
	for j in range(W):
		u = 0
		l = 0
		if j > 0 and a[i][j - 1] != '#':
			l = dp[i][j - 1]
		if i > 0 and a[i - 1][j] != '#':
			u = dp[i - 1][j]
		dp[i][j] += u + l
print(dp[H - 1][W - 1] % (10 ** 9 + 7))


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


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


(N, M) = map(int, input().split())
maze = [input() for _ in range(N)]
dp = [[0] * M for _ in range(N)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(N):
	for j in range(M):
		if maze[i][j] != '#':
			if i - 1 >= 0:
				dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod
			if j - 1 >= 0:
				dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod
print(dp[N - 1][M - 1])


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


(h, w) = map(int, input().split())
l = [[0] * w] * h
m = [''] * h
for k in range(h):
	m[k] = input()
l[0][0] = 1
for k in range(h):
	for j in range(w):
		if m[k][j] == '#':
			l[k][j] = 0
		elif k == 0:
			if j != 0:
				l[k][j] = l[0][j - 1]
		elif j == 0:
			if k != 0:
				l[k][j] = l[k - 1][j]
		else:
			l[k][j] = l[k - 1][j] + l[k][j - 1]
print(l[h - 1][w - 1] % 1000000007)


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
grid = tuple((tuple(map(lambda x: x == '.', input())) for _ in range(H)))
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][1] = 1
for x in range(H):
	for y in range(W):
		if grid[x][y]:
			dp[x + 1][y + 1] = (dp[x][y + 1] + dp[x + 1][y]) % MOD
print(dp[H][W])


(h, w) = map(int, input().split())
mod = 10 ** 9 + 7
G = [['#'] * (w + 1) for _ in range(h + 1)]
for i in range(1, h + 1):
	G[i] = ['#'] + list(input())
A = [[0] * (w + 1) for i in range(h + 1)]
A[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 G[i][j] == '.':
			A[i][j] = (A[i - 1][j] + A[i][j - 1]) % mod
print(A[-1][-1])


(h, w) = map(int, input().split())
grid1 = [['#'] * (w + 2) for i in range(h + 2)]
grid2 = [[0] * (w + 2) for i in range(h + 2)]
for i in range(h):
	grid1[i + 1][1:-1] = list(input())
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if i == j == 1:
			grid2[i][j] = 1
		elif grid1[i][j] == '.':
			grid2[i][j] = (grid2[i - 1][j] + grid2[i][j - 1]) % (10 ** 9 + 7)
print(grid2[h][w])


div = 10 ** 9 + 7
(h, w) = map(int, input().split())
dp = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
	a_h = input()
	for j in range(w):
		if (i == 0) & (j == 0):
			dp[i + 1][j + 1] = 1
		elif a_h[j] == '.':
			dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % div
print(dp[h][w])


(n, m) = map(int, input().split())
grid = []
for i in range(n):
	temp = list(input())
	grid.append(temp)
dp = [[0 for _ in range(m)] for i in range(n)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(n):
	for j in range(m):
		if grid[i][j] == '#':
			continue
		if i > 0:
			dp[i][j] += dp[i - 1][j] % mod
		if j > 0:
			dp[i][j] += dp[i][j - 1] % mod
print(dp[n - 1][m - 1] % mod)


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[1][1] = 1
for r in range(1, H + 1):
	for c in range(1, W + 1):
		if r == 1 and c == 1:
			continue
		if a[r - 1][c - 1] == '#':
			continue
		else:
			dp[r][c] = (dp[r - 1][c] + dp[r][c - 1]) % MOD
print(dp[H][W])


INF = float('inf')
mod = 10 ** 9 + 7
(h, w) = map(int, input().split())
G = []
for _ in range(h):
	s = input()
	G.append(s)
dp = [[-INF for i in range(w + 1)] for j in range(h + 1)]
dp[1][1] = 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if G[i - 1][j - 1] == '#':
			continue
		if i == 1 and j == 1:
			continue
		dp[i][j] = max(0, dp[i - 1][j]) + max(0, dp[i][j - 1])
		dp[i][j] %= mod
print(dp[h][w])


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
dp = [1] + [0] * (w - 1)
for i in range(h):
	dp[0] = int(dp[0] == 1 and a[i][0] == '.')
	for j in range(1, w):
		dp[j] = int(a[i][j] == '.') * (dp[j] + dp[j - 1]) % 1000000007
print(dp[-1])


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
G = [readline().rstrip() for i in range(H)]
DIV = 10 ** 9 + 7
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][1] = 1
for i in range(H):
	for j in range(W):
		if G[i][j] == '#':
			dp[i + 1][j + 1] = 0
			continue
		dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
		dp[i + 1][j + 1] %= DIV
print(dp[-1][-1])


(H, W) = map(int, input().split())
a = [list(input()) for i in range(H)]
dp = [[0] * W for i in range(H)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(H):
	for j in range(W):
		if a[i][j] == '#':
			continue
		if j > 0:
			dp[i][j] += dp[i][j - 1]
		if i > 0:
			dp[i][j] += dp[i - 1][j]
		dp[i][j] %= mod
print(dp[-1][-1])


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


(H, W) = map(int, input().split())
field = ['#' * (W + 2)]
field += ['#' + input() + '#' for _ in range(H)]
field += ['#' * (W + 2)]
dp = [[0] * (W + 2) for _ in range(H + 2)]
dp[1][1] = 1
for i in range(H + 2):
	for j in range(W + 2):
		if field[i][j] == '.':
			dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1], dp[i][j])
print(dp[H][W] % 1000000007)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
(h, w) = map(int, input().split())
wall = '#' * (w + 2)
MAP = [wall]
for _ in range(h):
	MAP.append('#' + input().strip() + '#')
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])


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


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


MOD = 10 ** 9 + 7
(h, w) = map(int, input().split())
grid = '#' * (w + 2)
for _ in range(h):
	grid += '#' + input() + '#'
grid += '#' * (w + 2)
D = [0] * len(grid)
start = w + 3
goal = -(w + 4)
D[start] = 1
for i in range(start + 1, len(grid)):
	if grid[i] == '#':
		continue
	D[i] = (D[i - 1] + D[i - (w + 2)]) % MOD
print(D[goal])


(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
MOD = 10 ** 9 + 7
dp = [[0] * 1100 for _ in range(1100)]
dp[1][1] = 1
for h in range(1, H + 1):
	for w in range(1, W + 1):
		if h == 1 and w == 1:
			continue
		if a[h - 1][w - 1] == '#':
			dp[h][w] = 0
		else:
			dp[h][w] += (dp[h - 1][w] + dp[h][w - 1]) % MOD
print(dp[H][W] % MOD)


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


(h, w) = map(int, input().split())
a = []
mod = 10 ** 9 + 7
for i in range(h):
	a.append([s for s in input()])
dp = [[0] * w for i in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		tasu = 0
		if j > 0 and a[i][j - 1] == '.':
			tasu += dp[i][j - 1]
		if i > 0 and a[i - 1][j] == '.':
			tasu += dp[i - 1][j]
		dp[i][j] = tasu % mod + dp[i][j]
print(dp[h - 1][w - 1] % mod)


mod = 1000000007
(H, W) = map(int, input().split())
root = []
for _ in range(H):
	s = list(input())
	root.append(s)
dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
	for w in range(W):
		if root[h][w] == '#':
			continue
		if h != 0 or w != 0:
			dp[h][w] = (dp[h - 1][w] + dp[h][w - 1]) % mod
print(dp[H - 1][W - 1])


import itertools
MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
A = [input() for _ in range(H)]
dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
dp[1][1] = 1
it = itertools.product(range(H), range(W))
next(it)
for (h, w) in it:
	if A[h][w] == '.':
		dp[h + 1][w + 1] = (dp[h][w + 1] + dp[h + 1][w]) % MOD
print(dp[H][W])


(H, W) = map(int, input().split())
G = [list(input()) for i in range(H)]
mod = 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 G[h][w] == '#':
			continue
		dp[h][w] += (dp[h - 1][w] + dp[h][w - 1]) % mod
print(dp[-1][-1])


(h, w) = map(int, input().split())
c = []
for i in range(h):
	c += [list(input())]
d = [[0 for i in range(w)] for j in range(h)]
d[0][0] = 1
for i in range(1, w):
	d[0][i] = d[0][i - 1] * (c[0][i] == '.')
for i in range(1, h):
	d[i][0] = d[i - 1][0] * (c[i][0] == '.')
for i in range(1, h):
	for j in range(1, w):
		d[i][j] = (d[i][j - 1] + d[i - 1][j]) * (c[i][j] == '.')
print(d[-1][-1] % (10 ** 9 + 7))


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


(h, w) = map(int, input().split())
grid = []
for _ in range(h):
	grid.append(input())
dp = [0] * (w + 1)
dp[1] = 1
for i in grid:
	newdp = dp[:]
	for (j, k) in enumerate(i):
		newdp[j + 1] = dp[j + 1] + newdp[j] if k == '.' else 0
	dp = newdp
print(dp[-1] % (10 ** 9 + 7))


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


(h, w) = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][0] = 1
for i in range(h):
	a = input()
	for (j, k) in enumerate(a):
		if i == 0 and j == 0:
			continue
		if k != '#':
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[h - 1][w - 1])


(H, W) = map(int, input().split())
grid = []
m = 10 ** 9 + 7
for i in range(H):
	a = list(input())
	grid.append(a)
dp = [[0] * (W + 3) for _ in range(H + 3)]
for i in reversed(range(H)):
	for j in reversed(range(W)):
		dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
		dp[H - 1][W - 1] = 1
		if grid[i][j] == '#':
			dp[i][j] = 0
print(dp[0][0] % m)


(H, W) = map(int, input().split())
S = [[a for a in input()] for _ in range(H)]
mod = 10 ** 9 + 7
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 S[i - 1][j - 1] == '#':
			continue
		if i == 1 and j == 1:
			continue
		DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
		DP[i][j] %= mod
print(DP[-1][-1])


(h, w) = map(int, input().split())
grid = [['#'] * (w + 2)] + [list('#' + input() + '#') for x in range(h)] + [['#'] * (w + 2)]
mod = 10 ** 9 + 7
dp = [[0] + [1] + [0] * w] + [(w + 2) * [0] for i in range(h)] + [[0] * (w + 2)]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if grid[i][j] == '#':
			dp[i][j] = 0
		else:
			dp[i][j] = sum((dp[i + s][j + t] % mod for (s, t) in ((0, -1), (-1, 0)))) % mod
print(dp[i][j] % mod)


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for i in range(H):
	for k in range(W):
		if i + 1 < H and grid[i + 1][k] != '#':
			dp[i + 1][k] += dp[i][k]
		if k + 1 < W and grid[i][k + 1] != '#':
			dp[i][k + 1] += dp[i][k]
		dp[i][k] %= MOD
print(dp[H - 1][W - 1] % MOD)


IN = lambda : list(map(int, input().split()))
(h, w) = IN()
A = [['#'] * (w + 1)] + [['#'] + list(input()) for i in range(h)]
C = [[0] * (w + 1) for i in range(h + 1)]
C[1][1] = 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if A[i][j] == '.' and (not (i == 1 and j == 1)):
			C[i][j] = C[i - 1][j] + C[i][j - 1]
print(C[-1][-1] % (10 ** 9 + 7))


mod = 1000000007

def cnt(i, j):
	if 0 <= i - 1 < H:
		dp[i][j] += dp[i - 1][j]
	if 0 <= j - 1 < W:
		dp[i][j] += dp[i][j - 1]
(H, W) = list(map(int, input().split()))
grid = [[i for i in input()] for j in range(H)]
dp = [[0] * W for i in range(H)]
dp[0][0] = 1
for h in range(H):
	for w in range(W):
		if grid[h][w] == '.':
			cnt(h, w)
print(dp[H - 1][W - 1] % mod)


(H, W) = list(map(int, input().split()))
S = []
for i in range(H):
	S.append(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 S[i][j] == '.':
			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])


(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
WARU = 10 ** 9 + 7
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] == '#':
			continue
		dp[i][j] %= WARU
		dp[i + 1][j] += dp[i][j]
		dp[i][j + 1] += dp[i][j]
print(dp[H - 1][W - 1])


(h, w) = map(int, input().split())
wall = [list(input()) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if i == 0 and j == 0:
			continue
		tmp = 0
		if i > 0 and wall[i - 1][j] == '.':
			tmp += dp[i - 1][j]
		if j > 0 and wall[i][j - 1] == '.':
			tmp += dp[i][j - 1]
		dp[i][j] += tmp
print(dp[h - 1][w - 1] % 1000000007)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(input())
ans = [0] * (m + 1)
ans[1] = 1
for i in range(n):
	for j in range(m):
		if a[i][j] == '.':
			ans[j + 1] += ans[j]
			ans[j + 1] %= 1000000007
		else:
			ans[j + 1] = 0
print(ans[m])


(H, W) = map(int, input().split())
g = [list(input()) for _ in range(H)]
mod = int(1000000000.0) + 7
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 g[i][j] == '#':
			continue
		if i + 1 < H:
			dp[i + 1][j] += dp[i][j] % mod
		if j + 1 < W:
			dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)


MOD = 10 ** 9 + 7
(H, W) = map(int, input().split())
G = [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 G[i][j] == '#':
			continue
		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[H - 1][W - 1])


(r, c) = map(int, input().split())
m = []
for i in range(r):
	m.append(list(input()))
dp = [[0 for j in range(c)] for i in range(r)]
dp[0][0] = 1
for i in range(0, r):
	for j in range(0, c):
		if m[i][j] == '.':
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
print(dp[r - 1][c - 1] % 1000000007)


(H, W) = map(int, input().split())
mod = 1000000007
a_matrix = []
for _ in range(H):
	a_matrix.append(list(input()))
dp = [[0 for w in range(W + 1)] for h in range(H + 1)]
dp[1][0] = 1
for w in range(1, W + 1):
	for h in range(1, H + 1):
		if a_matrix[h - 1][w - 1] == '.':
			dp[h][w] = (dp[h - 1][w] + dp[h][w - 1]) % mod
		else:
			dp[h][w] = 0
print(dp[H][W])


(h, w) = map(int, input().split())
a = [input() for i in range(h)]
mod = 10 ** 9 + 7
d = [[0] * w for i in range(h)]
d[0][0] = 1
for i in range(h):
	for j in range(w):
		if i + 1 < h and a[i + 1][j] == '.':
			d[i + 1][j] += d[i][j]
			d[i + 1][j] %= mod
		if j + 1 < w and a[i][j + 1] == '.':
			d[i][j + 1] += d[i][j]
			d[i][j + 1] %= mod
print(d[-1][-1])


(H, W) = map(int, input().split())
X = [[[0, 1][a == '#'] for a in input()] for i in range(H)]
Y = [[0] * W for _ in range(H)]
Y[0][0] = 1
P = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		if X[i][j] == 0:
			if i > 0:
				Y[i][j] += Y[i - 1][j]
			if j > 0:
				Y[i][j] += Y[i][j - 1]
			Y[i][j] %= P
print(Y[-1][-1])


(y_map, x_map) = map(int, input().split())
field_map = [list(input()) for i in range(y_map)]
dp = [[0 for i in range(x_map + 1)] for j in range(y_map + 1)]
dp[1][1] = 1
for i in range(y_map):
	for j in range(x_map):
		if field_map[i][j] == '.':
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j] + dp[i][j + 1])
		else:
			dp[i + 1][j + 1] = 0
print(dp[-1][-1] % (10 ** 9 + 7))


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


(H, W) = map(int, input().split())
MAP = [input() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
M = 10 ** 9 + 7
for i in range(H):
	for j in range(W):
		if MAP[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] %= M
print(dp[-1][-1])


mo = 10 ** 9 + 7
(h, w) = map(int, input().split())
m = [[0] * (w + 2) for i in range(h + 2)]
for i in range(h):
	for (j, s) in enumerate(input()):
		m[i + 1][j + 1] = 0 if s == '#' else 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if i * j == 1:
			0
		elif m[i][j] != 0:
			m[i][j] = m[i - 1][j] + m[i][j - 1]
			m[i][j] %= mo
print(m[h][w] % mo)


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


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
M = 10 ** 9 + 7
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = 1
for i in range(h):
	for j in range(w):
		dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) * (g[i][j] == '.')
print(dp[-1][-1] % M)


(h, w) = map(int, input().split())
grid = []
for i in range(h):
	grid.append(input())
dp = [[0 for i in range(w)] for i in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if grid[i][j] != '#':
			if i - 1 >= 0:
				dp[i][j] += dp[i - 1][j]
			if j - 1 >= 0:
				dp[i][j] += dp[i][j - 1]
mod = 1000000007
print(dp[-1][-1] % mod)


(h, w) = map(int, input().split())
(m, mod) = ([], 10 ** 9 + 7)
for i in range(h):
	m.append(input())
dp = [[0] * w for i in range(h)]
dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if m[i][j] == '.':
			if i == 0 and j != 0:
				dp[i][j] = dp[i][j - 1]
			elif i != 0 and j == 0:
				dp[i][j] = dp[i - 1][j]
			elif i != 0 and j != 0:
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[h - 1][w - 1])


import sys
sys.setrecursionlimit(10 ** 8)
(h, w) = map(int, input().split())
a = []
dp = {}
dp[h - 1, w - 1] = 1
for i in range(h):
	a.append(list(input()))

def foo(i, j):
	if i >= h or j >= w:
		return 0
	if (i, j) in dp:
		return dp[i, j]
	ans = 0
	if i + 1 < h and a[i + 1][j] == '.':
		ans += foo(i + 1, j)
	if j + 1 < w and a[i][j + 1] == '.':
		ans += foo(i, j + 1)
	dp[i, j] = ans % (1000000000.0 + 7)
	return dp[i, j]
print(int(foo(0, 0)))