Steps

Description

给出N-1对括号,求出N-1对括号的正确匹配方案数(对1000000007取模)的结果。
我们认为一个括号匹配,即对任意一个')',在其左侧都有一个'('与它匹配,且他们形成一一映射关系。

Input

第一行:一个整数N

Output

第一行:一个整数Ans

Sample

Input 1

4

Output 1

5

Input 2

50

Output 2

765348450

Limitation

对于10%的数据:n≤10
对于35%的数据:n≤500
对于70%的数据:n≤5000
对于100%的数据:n≤1000000
时间限制1秒,空间限制128MB

信息

难度
4
分类
(无)
标签
(无)
递交数
70
已通过
29
通过率
41%
上传者

相关

在下列比赛中:

ACM模拟赛