题目描述

你拿到了n对括号，每对括号由一个左括号和一个右括号组成。现在你可以打乱重组这2n个括号，问重组后满足是合法括号序列的结果有多少种？

将计算结果对$10^9 +7$取模

输入格式

一个正整数n，n<=1000

输出格式

输出答案，对$10^9$取模

3

5

Hint

样例中，当n=3时，合法的括号序列有 ()()() ()(()) ((())) (())() (()())