• 전형적인 2차원 DP. puddle이 없다면 최단 경로의 수를 조합으로 바로 계산할 수 있지만, 이 경우는 DP로 풀어야 한다.
• 어떤 좌표까지 가는 경로의 수는, 왼쪽에서 가는 경로의 수 + 위쪽에서 가는 경로의 수가 된다. 점화식은 dp[r][c] = dp[r-1][c] + dp[r][c-1] 이고, (r,c)가 puddle일때는 dp[r][c]=0 으로 처리하면 된다.
• 총 시간복잡도는, n*m DP 테이블을 채우는 데에는 드는 O(nm).

"""Solution code for "Programmers 42898. 등굣길".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42898
- Solution link: http://www.teferi.net/ps/problems/programmers/42898
"""

MOD = 1_000_000_007


def solution(m, n, puddles):
    puddles_set = {(r - 1, c - 1) for c, r in puddles}
    dp_cur = [1] + [0] * (m - 1)
    for r in range(n):
        dp_cur, dp_prev = [], dp_cur
        for c in range(m):
            if (r, c) in puddles_set:
                dp_cur.append(0)
            elif c == 0:
                dp_cur.append(dp_prev[c])
            else:
                dp_cur.append((dp_cur[-1] + dp_prev[c]) % MOD)
    return dp_cur[-1]