No testdata at current.

Background

• 合法括号序列的定义是：
• 空串是合法括号序列
• 如果 A 是合法括号序列，那么 (A) 也是合法括号序列
• 如果 A 和 B 都是合法括号序列，那么 AB 也是合法括号序列
• 没有其他合法括号序列了
• 如 ()(()) 就是一个合法括号序列，())( 就不是。

Description

• 现在，给你 $n$ 个左括号和 $n$ 个右括号，请问用他们一共能组成多少个不同的合法括号序列？（全用上）

Format

Input

一个正整数 $n \ (1≤n≤5000)$

Output

一个整数，表示答案（答案可能很大）

Samples

1

1

30

3814986502092304

Limitation

样例1：由1个左括号和1个右括号只能组成一个合法括号序列：()。样例2：我有一个很好的证明，我能写下但我不想写。