펭귄 네비게이터
시간 제한1초메모리 제한1024 MB
2 곱하기 N 격자의 칸에 1부터 2N까지 번호를 매길 때, (1,1)에서 (2,N)으로 가는 모든 오른쪽 또는 아래 이동이 번호를 증가시키는 경우의 수를 구한다.
문제
펭귄은 현재 에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 이다. 하지만 누군가가 얼음길을 다 깨뜨려서 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 예정이다. 얼음길은 크기이며, 얼음마다 중복 없이 부터 까지의 번호를 붙일 수 있다. 이 펭귄들에겐 특이한 습성이 있다. 펭귄은 현재 위치의 오른쪽이나 아래로만 이동한다. 하지만 이동한 곳의 번호가 원래 위치의 숫자보다 커야만 한다. 펭귄이 어떤 움직임을 하든지 무조건 집으로 갈 수 있게 만드는 얼음길의 개수를 구하는 프로그램을 작성해보자.
입력
첫 번째 줄에는 얼음길 가로의 길이 ()이 주어진다.
출력
첫째 줄에 만들어지는 얼음길의 개수를 로 나눈 나머지를 출력한다.