跨年夜的钟声即将敲响，窗外的烟花照亮了夜空，刚刚经历了考研的Beaten却还在自习室里埋头钻研408数据结构。显然，考研的题目没有难倒他，但是他想知道是否会难倒屏幕前的你呢？

Beaten计划在跨年夜的 分钟里，每一分钟完成一道和括号相关的小题，每一道小题的结果会对应一个括号字符——要么是左括号 ，要么是右括号 。当 分钟的刷题结束后，所有字符会按时间顺序组成一个长度为 的括号序列。现有以下约束条件：
1.因为总时长是 分钟，所以最终的括号序列长度必须恰好为 ；同时，Beaten刷到的左括号和右括号数量必须完全相等，各自都为 个——这是因为每一道左括号对应的小题，都需要匹配一道右括号对应的小题才能算完成。
2.在任意一段连续的刷题时间内(对应序列的任意一个前缀子串，从第 分钟到第 分钟，)，Beaten完成的左括号小题数量，必须大于或等于右括号小题数量。这是因为只有先掌握了左括号对应的知识点，才能顺利解决右括号对应的配套习题，反之则会导致刷题卡顿，无法推进。
3.Beaten刷题时喝了 杯咖啡，每杯咖啡对应一种口味，甚至给出了咖啡口味的列表，但实际上，咖啡的口味和括号序列的合法性没有任何关系，只是为了营造跨年氛围，对解题没有任何帮助。

请你统计出满足所有约束条件的合法括号序列的总数。

输入一个整数 （），既表示括号的总对数，也表示Beaten喝的咖啡杯数、跨年倒计时的分钟数的一半。

输出一个整数，表示满足条件的合法括号序列的总数。

1

1

仅1对括号，唯一合法的序列就是左括号后接右括号，满足 “任意前缀左括号数 ≥ 右括号数” 的约束。

3

5

：连续3个左括号后接3个右括号；
：先写2个左括号，匹配1个右括号，再写1个左括号，最后匹配2个右括号；
：先完成一对嵌套括号，再完成一对并列括号；
：先完成一对并列括号，再完成一对嵌套括号；
：3对括号依次并列。

无论你是否参加了今年的408计算机学科专业基础综合考试，相信你在遇到括号匹配问题时一定会想起ta