10살의 동적 계획법

어느 날 저녁. 늘 그렇듯 당신이 거실에서 텔레비전을 보고 있는데, 초등학교 5학년인 여동생이 고민을 털어놓았다. 이야기를 들어 보니, 오늘 학교에서 나온 산수 문제가 어려워서 이해하지 못했으니 풀이 방법을 가르쳐 달라는 것이었다.

여동생을 괴롭히는 문제는 "길이 바둑판 모양으로 난 도시에서 집 (0, 0)에서 학교 (N, M)까지 최단 거리로 가는 방법은 몇 가지인가?"라는 것이었다. 물론 당신에게는 식은 죽 먹기보다 쉬운 문제이다. 곧바로 위와 같은 그림을 그려서 "집 (0, 0)에서부터 차례대로 덧셈해 나가면 풀 수 있어"라고 가르쳐 주었다.

그런데 그 말을 듣고도 여동생은 여전히 뭔가를 골똘히 생각하며 고개를 숙이고 있었다. 당신은 자신의 설명 방식이 나빴던 게 아닐까 생각했지만, 그런 것 같지는 않았다.

꼬박 3분쯤 고민했을까. 여동생은 천천히 고개를 들더니 당신에게 이렇게 말했다.

"그치만 나라면, 분명 학교에 가는 길에 K번쯤은 딴 데 들렀다 갈 거야……. 있지 오빠, 그러면 답은 몇 가지가 돼?"

큰일이다. 형의 위엄을 지키기 위해서라도 이 문제에 반드시 답해야 한다.

이 문제를 정식화하면 다음과 같다.

• 점 (0, 0)에서 점 (N, M)까지 바둑판 모양의 길을 따라 가는 방법은 몇 가지인가 답하라.
• 기본적으로는 오른쪽이나 위로 1칸씩 가지만, 도중에 정확히 K번만 딴 데를 들른다.
• "딴 데를 들른다"는 것은 왼쪽이나 아래로 1칸 가는 것이다.
• K번의 딴 데 들르기를 마치지 않았다면, 일단 점 (N, M)에 도착한 뒤에도 계속 걷는다. 도중에 점 (0, 0)으로 되돌아오는 경우도 있다.
• 집은 이 도시의 구석에 있으므로, X 좌표나 Y 좌표가 음수가 되는 점에는 들어갈 수 없다.
• 그러나 X 좌표가 N보다 큰 점, 또는 Y 좌표가 M보다 큰 점에는 들어갈 수 있다.

N M K

입력의 첫째 줄에는 정수 N (1 ≤ N ≤ 100,000)과 정수 M (1 ≤ M ≤ 100,000)과 정수 K (0 ≤ K ≤ 10,000)가 이 순서대로 공백으로 구분되어 적혀 있다. 정수 N은 학교의 X 좌표를, 정수 M은 학교의 Y 좌표를, 정수 K는 딴 데 들르는 횟수를 나타낸다.

점 (0, 0)에서 점 (N, M)까지 K번 딴 데를 들르며 가는 방법. 그 총수를 1,000,000,007로 나눈 나머지를 출력하라. 1,000,000,007은 소수이다.