题目描述

小刚在学习编程时，遇到了括号匹配的问题。他想知道：如果用 $n$ 个左括号 ( 和 $n$ 个右括号 ) 排成一列，使得从左到右扫描时，任意位置左括号的数量都不小于右括号的数量，那么一共有多少种合法的排列方案？

例如 $n=2$ 时，有两种合法方案：(() ) 和 (())。

输入格式

输入一个正整数 $n$。

输出格式

输出方案数对 $100$ 取模的结果。

样例

2

2

提示

数据范围

$1 \le n \le 100$。