1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(m, n, puddles):
    dx, dy = (0, -1), (-1, 0)

    board = [[0]*m for _ in range(n)]
    board[0][0] = 1
    for a, b in puddles:
        board[a-1][b-1] = -1
    print(board)
    for x in range(n):
        for y in range(m):
            if board[x][y] == -1:
                continue

            for i in range(2):
                nx, ny = x + dx[i], y + dy[i]

                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue

                prev = board[nx][ny]
                if prev != -1:
                    board[x][y] += prev

    return board[n-1][m-1]%1000000007