아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

펭귄 네비게이터

시간 제한1초메모리 제한1024 MB

요약
2 곱하기 N 격자의 칸에 1부터 2N까지 번호를 매길 때, (1,1)에서 (2,N)으로 가는 모든 오른쪽 또는 아래 이동이 번호를 증가시키는 경우의 수를 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 조합론, 수학, 구현
정답자
아직 제출이 없습니다

문제

펭귄은 현재 (1,1)(1, 1)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 (2,N)(2, N)이다. 하지만 누군가가 얼음길을 다 깨뜨려서 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 예정이다. 얼음길은 2×N2 \times N 크기이며, 얼음마다 중복 없이 11부터 2N2N까지의 번호를 붙일 수 있다. 이 펭귄들에겐 특이한 습성이 있다. 펭귄은 현재 위치의 오른쪽이나 아래로만 이동한다. 하지만 이동한 곳의 번호가 원래 위치의 숫자보다 커야만 한다. 펭귄이 어떤 움직임을 하든지 무조건 집으로 갈 수 있게 만드는 얼음길의 개수를 구하는 프로그램을 작성해보자.

입력

첫 번째 줄에는 얼음길 가로의 길이 NN (1≤N≤10 0001 \leq N \leq 10\,000)이 주어진다.

출력

첫째 줄에 만들어지는 얼음길의 개수를 109+710^9+7로 나눈 나머지를 출력한다.

예제1

  1. 예제 1

    입력
    3
    
    예상 출력
    5