该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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