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

"""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()

• Dependency: teflib.combinatorics.catalan