다이나믹이 뭐예요?

안녕하세요! 저는 오늘 다이나믹 프로그래밍(동적 계획법)을 설명하러 온 욱제예요. 다이나믹은 이름은 거창하지만 개념은 간단해요. 기본 아이디어는 이미 계산한 값을 다시 사용해서(어려운 말로 메모이제이션이라고 해요) 똑같은 연산이 반복되는 횟수를 줄이는 거예요.

예를 들어 5번째 피보나치 수 $F(5)$를 구하는 과정을 살펴볼게요.

같은 함수가 쓸데없이 여러 번 호출되는 게 보이죠? $F(2)$와 $F(3)$을 미리 구해 두고 $F(4)$를 구할 때 그 값을 쓰면 불필요한 호출을 줄일 수 있어요. 조금 엄밀하게 이야기해 볼게요. 피보나치 수열은 수학적으로 $F(n) = F(n-1) + F(n-2)$로 정의할 수 있죠? 이런 식을 세우는 과정을 점화식을 세운다고 해요. 문제 조건에 맞는 식을 만들고 그 식을 그대로 코드로 옮기면 다이나믹을 아주 쉽게 구현할 수 있어요.

물론 다차원 배열로도 할 수 있어요! 오른쪽과 아래쪽으로만 움직일 수 있을 때 $D[1][1]$에서 $D[x][y]$까지 도달하는 경우의 수를 구하는 문제는 모든 경우를 일일이 계산할 필요가 없어요. $(i, j)$에 도달하는 누적 경우의 수를 $D[i][j]$라고 하면 $D[i][j] = D[i-1][j] + D[i][j-1]$이라는 점화식을 세워서 풀 수 있죠.

어때요? 다이나믹, 어렵지 않죠? 이제 문제를 풀어 볼게요!

→, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위 $(1, 1)$에서 출발해 오른쪽 아래 $(n, m)$에 도착하는 경우의 수를 구하여라.

시작!

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다. (1 ≤ n, m ≤ 1,000)

$(1, 1)$에서 $(n, m)$에 도달하는 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있으므로 1,000,000,007($= 10^9 + 7$)로 나눈 나머지를 출력한다.