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