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}\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.

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.



Sample input:
3 4
...#
.#..
....


Sample output:
3

Submission status: Accepted

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

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

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

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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

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

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

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

    dp[r][0] = 1

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

    dp[0][c] = 1


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

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


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

Submission status: Accepted

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


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

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


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


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

Submission status: Accepted

Solution code:
MOD = int(1e9 + 7)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
dp = [[0] * w for i in range(h)]
dp[0][0] = 1

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

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        elif i == 0:
            if grid[i][j-1] == ".":
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if grid[i-1][j] == ".":
                dp[i][j] = dp[i-1][j]
        else:
            if grid[i-1][j] == "#" and grid[i][j-1] == "#":
                continue
            elif grid[i-1][j] == "#":
                dp[i][j] = dp[i][j-1]
            elif grid[i][j-1] == "#":
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = mod(dp[i-1][j] + dp[i][j-1])
                
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:


MOD = 1000000007

h, w = map(int, raw_input().split())
grid = []
for _ in range(h):
    grid.append(raw_input())

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

Submission status: Accepted

Solution code:
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]=( (dp[j]+dp[j-1]) % 1000000007) if a[i][j]=='.' else 0
print(dp[-1])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
MOD = pow(10, 9) + 7

h, w = map(int, raw_input().strip().split())
dp = [[0 for i in xrange(w + 1)] for j in xrange(h + 1)]

grid = [['.' for i in xrange(w)] for j in xrange(h)]
for i in xrange(h):
    s = raw_input()
    for j in xrange(len(s)):
        if s[j] == '#': grid[i][j] = '#'

dp[h - 1][w - 1] = 1
for i in xrange(h - 1, -1, -1):
    for j in xrange(w - 1, -1, -1):
        if i == h - 1 and j == w - 1: continue
        if grid[i][j] == '#': continue
        dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
        if dp[i][j] >= MOD: dp[i][j] -= MOD

print dp[0][0]

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a=[ list(input()) for _ in range(h)]
mod=int((1e9)+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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
mod = 7 + 10**9
DP = [[0 for w in range(W)] for h in range(H)]
for w in range(W):
    if A[0][w] == "#":break
    else: DP[0][w] = 1
for h in range(H):
    if A[h][0] == "#": break
    else: DP[h][0] = 1

for h in range(1, H):
    for w in range(1, W):
        if A[h][w] == ".":
            DP[h][w] = (DP[h-1][w] + DP[h][w-1]) % mod

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

Submission status: Accepted

Solution code:
DIV = 10**9 + 7
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())
dp = [[0 for _ in range(W)] for _ in range(H)]

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

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

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

MOD = 1000000007
H, W = map(int, input().split())
grid = stdin.read().splitlines()
dp = [[1] * W for _ in range(H)]

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

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

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

MOD = 1000000007
H, W = map(int, input().split())
grid = stdin.read().splitlines()
dp = [[1] * W for _ in range(H)]

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

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

Submission status: Accepted

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

a=[]
for i in range(h):
    a.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>0 and a[i-1][j]!="#":
            dp[i][j]+=dp[i-1][j]
        if j>0 and a[i][j-1]!="#":
            dp[i][j]+=dp[i][j-1]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・自力AC
・数え上げDP
・計算量O(H*W)=1000*1000=100万、pythonで1.4秒、pypyで0.8秒くらい。
・貰うDPを配るDPにしてみた。
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

# 四方に一回り大きいグリッドを作る
grid = [['#'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]

dp = [[0] * (W+2) for i in range(H+2)]
# スタート地点に1通りを初期値設定
dp[1][1] = 1
for i in range(1,H+1):
    for j in range(1, W+1):
        # 現在位置が壁なら何もできない
        if grid[i][j] == '#':
            continue
        # 下が壁でなければ、値を送る
        if grid[i+1][j] != '#':
             dp[i+1][j] += dp[i][j]
        # 右が壁でなければ、値を送る
        if grid[i][j+1] != '#':
            dp[i][j+1] += dp[i][j]
# ゴール地点の値を確認する
print(dp[H][W] % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

# 四方に一回り大きいグリッドを作る
grid = [['#'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]

dp = [[0] * (W+2) for i in range(H+2)]
# スタート地点に1通りを初期値設定
dp[1][1] = 1
for i in range(1,H+1):
    for j in range(1, W+1):
        # 現在位置が壁なら何もできない
        if grid[i][j] == '#':
            continue
        # 上が壁でなければ、値を持ってくる
        if grid[i-1][j] != '#':
            dp[i][j] += dp[i-1][j]
        # 左が壁でなければ、値を持ってくる
        if grid[i][j-1] != '#':
            dp[i][j] += dp[i][j-1]
# ゴール地点の値を確認する
print(dp[H][W] % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

H, W = map(int, input().split())
Ass = [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 Ass[i][j] == '#': continue
        dp[i][j] %= MOD
        if i < H-1:
            dp[i+1][j] += dp[i][j]
        if j < W-1:
            dp[i][j+1] += dp[i][j]

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

Submission status: Accepted

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

dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(h):
    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]) % mod
        if j + 1 < w and a[i][j + 1] == '.':
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 16:41:33 2019
DP_H
@author: maezawa
"""

mod = 10**9+7
h, w = list(map(int, input().split()))
a = [['#']*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
    ahi = input()
    ahi = '#' + ahi + '#'
    a[i] = list(ahi)
    
#print(*a, sep='\n')

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

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            continue
        else:
            b[i][j] += b[i][j-1] + b[i-1][j]
            b[i][j] = b[i][j] % mod

print(b[h][w])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    a = [[c for c in S()] for _ in range(h)]
    r = [[0]*w for _ in range(h)]
    r[0][0] = 1
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                continue
            if i > 0:
                r[i][j] += r[i-1][j]
            if j > 0:
                r[i][j] += r[i][j-1]
            r[i][j] %= mod

    return r[-1][-1]


print(main())

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
H,W=map(int, raw_input().split())
A=[ raw_input() for i in range(H) ]

dp=[ [ 0 for j 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 0<=i-1<H:   dp[i][j]+=dp[i-1][j]
			if 0<=j-1<W:   dp[i][j]+=dp[i][j-1]
	dp[i][j]%=mod

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [input() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
MOD = 10**9 + 7
dp[0][0] = 1
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            continue
        s = 0
        if hi-1>=0:
            s += dp[hi-1][wi]
        if wi-1>=0:
            s += dp[hi][wi-1]
        dp[hi][wi] += s
        dp[hi][wi] %= MOD

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

Submission status: Accepted

Solution code:
mod = int(1e9 + 7)
h, w = map(int, input().split())
MAP = ['#' * (w + 1)] + ['#' + 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])

Submission status: Accepted

Solution code:
mod = int(1e9 + 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])

Submission status: Accepted

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

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

flagH = 0
flagW = 0

for i in range(H):
  if a[i][0]=="." and flagH==0:
    dp[i][0]=1
  else:
    dp[i][0]=0
    flagH=1

for j in range(W):
  if a[0][j]=="." and flagW==0:
    dp[0][j]=1
  else:
    dp[0][j]=0
    flagW=1

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

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

Submission status: Accepted

Solution code:
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>0 and a[i-1][j]!='#':
            dp[i][j]+=dp[i-1][j]
        if j>0 and a[i][j-1]!='#':
            dp[i][j]+=dp[i][j-1]
        dp[i][j]=dp[i][j]%(10**9+7)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
raw_input = sys.stdin.readline
N,M = map(int,raw_input().split())
arr = []
for i in range(N):
    arr.append(list(raw_input()))
dp = [[0 for x in range(M)] for x in range(N)]
dp[0][0] = 1
mod = 1000000007
for i in range(N):
    for j in range(M):
        if arr[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[N-1][M-1]

Submission status: Accepted

Solution code:
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%(1e9+7)
	return dp[(i,j)]

print(int(foo(0,0)))

Submission status: Accepted

Solution code:
from sys import stdin

H, W = map(int, stdin.readline().split())
field = [1 for _ in range(H*W)]
for i in range(H):
    tmp = stdin.readline().rstrip()
    for j, c in enumerate(tmp):
        if c == '#':
            field[W*i+j] = 0

N = H*W
dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(1, N):
    if field[i]:
        if i < W:
            dp[i] = dp[i-1]
        elif i % W == 0:
            dp[i] = dp[i-W]
        else:
            dp[i] = dp[i-1] + dp[i-W]
            dp[i] = dp[i] % 1000000007
print(dp[N-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)

Submission status: Accepted

Solution code:
mm=1000000007

H,W= [int(x) for x in raw_input().split()]
S=["#"*(H+2)]
for i in range(H):
    S.append("#"+ raw_input() +"#")
S.append("#"*(H+2))
A=[ [0 for x in range(W+2)] for y in range(H+2)]
A[1][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]=="." and not (i==1 and j==1):
            A[i][j]= (A[i][j-1]+A[i-1][j])%mm
print(A[H][W])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
grid = [["#"]*(W+2) for i in range(H+2)]
for i in range(H):
    s = input()
    for j in range(W):
        grid[i+1][j+1] = s[j]
dp = [[0]*(W+2) for i in range(H+2)]
dp[1][1] = 1
for i in range(H):
    for j in range(W):
        if (i,j) == (0,0):
            continue
        dp[i+1][j+1] = 0
        if grid[i+1][j] == ".":
            dp[i+1][j+1] += dp[i+1][j]
        if grid[i][j+1] == ".":
            dp[i+1][j+1] += dp[i][j+1]
ans = dp[H][W] % (10**9 + 7)   
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
Grid=[input() for i in range(H)]
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 Grid[i][j]==".":
      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[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
H, W = [int(elem) for elem in input().split()]
grid = tuple(tuple(input()) for _ in range(H))
assert len(grid[0]) == W

dp = [[0] * W for _ in range(H)]
# for j in range(W):
#     if grid[]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if j > 0 and grid[i][j - 1] == ".":
            dp[i][j] += dp[i][j - 1]
        if i > 0 and grid[i - 1][j] == ".":
            dp[i][j] += dp[i - 1][j]
        dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

H, W = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		if h + w == 0:
			dp[h][w] = 1
		elif a[h][w] == "#":
			continue
		elif h == 0:
			dp[h][w] = dp[h][w-1]
		elif w == 0:
			dp[h][w] = dp[h-1][w]
		else:
			dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % MOD

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

H, W = map(int, input().split())
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		if h + w == 0:
			dp[h][w] = 1
		elif a[h][w] == "#":
			continue
		elif h == 0:
			dp[h][w] = dp[h][w-1]
		elif w == 0:
			dp[h][w] = dp[h-1][w]
		else:
			dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % MOD

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

Submission status: Accepted

Solution code:
# encoding: utf-8
H, W = map(int, input().split())
a = [list(input()) for i in range(H)]


tab = [0] * (H * W)

for i in range(H):
    for j in range(W):
        idx = i * W + j
        if i == j == 0: tab[idx] = 1
        elif a[i][j] == '#': continue
        elif i == 0: tab[idx] = tab[idx - 1]
        elif j == 0: tab[idx] = tab[idx - W]
        else:
            tab[idx] = (tab[idx - 1] + tab[idx - W]) % (10 ** 9 + 7)

print(tab[-1])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W = list(map(int, input().split()))
a = [list(input()) for _ in range(H)]
c = [[0 for _ in range(W)] for _ in range(H)]
# print(a)
mod = int(1e9 + 7)
c[0][0] = 1

for y in range(H):
    for x in range(W):
        if a[y][x] == "#":
            continue
        # print("x,y:",x,y)
        if x+1 < W and a[y][x+1] != "#":
            c[y][x+1] = c[y][x+1] + c[y][x]  % mod # right
        if y+1 < H and a[y+1][x] != "#":
            c[y+1][x] = c[y+1][x] + c[y][x]  % mod # right
        
        

# for i in range(H):
#     print(c[i])
print(c[H-1][W-1] % int(1e9+7))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]
mod=10**9+7
dp=[[0]*W for i in range(H)]
dp[0][0]=1
for i in range(H):
    for j in range(W):
        if i+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])

Submission status: Accepted

Solution code:

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
MOD = int(1e9)+7

dp = [[0]*W for _ in range(H)]
for w in range(W):
    if a[0][w]=="#":
        break
    dp[0][w] = 1
for h in range(H):
    if a[h][0]=="#":
        break
    dp[h][0] = 1
       
for h in range(H):
    for w in range(W):
        if h+1<H and w+1<W and a[h+1][w+1]==".":
            dp[h+1][w+1] = dp[h][w+1] + dp[h+1][w]
    #print(dp)
print(dp[-1][-1]%MOD)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
M = []
for i in range(H):
  M.append(input())
d = {}
d[(1,1)]=0
flag = False
for j in range(1,W):
  if flag or M[0][j]=="#":
    d[(1,j+1)] = 0
    flag = True
    continue
  d[(1,j+1)]=1
flag = False
for j in range(1,H):
  if flag or M[j][0]=="#":
    d[(j+1,1)] = 0
    flag = True
    continue
  d[(j+1,1)]=1
for l in range(1,H):
  for m in range(1,W):
    if M[l][m]==".":
      d[(l+1,m+1)]=(d[(l,m+1)]+d[(l+1,m)])%(1000000007)
    else :
      d[(l+1,m+1)] = 0
print(d[(H,W)])