====== 펭귄 네비게이터 ======

===== 풀이 =====
  * 결론적으로 [[ps:카탈랑 수]]가 되기는 하는데, 변환과정이 직관적으로 떠오르지는 않는다.
  * 조건을 만족하기 위해서는, 어떤 칸에 들어가는 수는 그 칸보다 왼쪽이나 위쪽에 있는 칸에 있는 수보다 커야 한다.
  * 이런 조건을 만족하는 얼음길이 있다고 할때, 얼음길을 괄호 문자열로 변환할수가 있다.
  * 문자열의 i번째 글자를, i번 수가 얼음길의 위쪽 칸에 있으면 (, 아래쪽 칸에 있으면 )가 된다고 하자. 조건을 만족하는 얼음길은 올바른 괄호문자열이 된다.
  * 이렇게 n개의 괄호쌍으로 만들어지는 올바른 괄호문자열의 갯수와 동일한 문제가 되므로, 답은 카탈랑수가 되고 O(n)에 구할수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 21739. 펭귄 네비게이터".

- Problem link: https://www.acmicpc.net/problem/21739
- Solution link: http://www.teferi.net/ps/problems/boj/21739

Tags: [catalan number]
"""

from teflib import combinatorics

MOD = 10**9 + 7


def main():
    N = int(input())
    print(combinatorics.catalan(N, MOD))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#catalan|teflib.combinatorics.catalan]]

{{tag>BOJ ps:problems:boj:골드_2}}