스노보드
시간 제한1초메모리 제한1024 MB
N행 M열 격자에서 아래 또는 대각선 아래로 이동하며 정확히 P개의 칸을 지나 맨 윗줄에서 맨 아랫줄까지 가는 경로의 수를 262로 나눈 나머지를 구한다.
문제
온고봉고는 스노보더이다. 그의 슬로프에는 그림과 같이 N개의 행에 각각 M개의 깃발이 놓여 있다. 온고봉고는 슬로프의 가장 위쪽에서 시작해 가장 아래쪽에서 끝나면서 정확히 P개의 깃발을 지나가려고 한다. 이때 그는 아래로만 미끄러져 내려갈 수 있으며, 같은 행의 바로 아래 깃발이나 바로 아래 행의 인접한 두 깃발 중 하나로 이동할 수 있다. 그가 목표를 이루는 방법은 몇 가지인가?
입력
표준 입력의 첫째 줄에서 N, M, P를 읽는다. (0 < N ≤ M ≤ 200, 0 < P < N + M)
출력
표준 출력의 한 줄에 구하는 방법의 수를 262로 나눈 나머지를 출력한다.
힌트
그림은 5개의 깃발을 지나 내려가는 열두 가지 방법 중 하나를 보여 준다. 또한 그림에 나온 슬로프에는 4개의 깃발을 지나 내려가는 방법이 3가지 더 있고, 6개의 깃발을 지나 내려가는 방법이 10가지 있다.