Misc [I]

Miscellaneous [I]

You want to know how many ways you can organise $n$ ( and ) brackets so the result string is balanced, that is, so that every closing ) bracket is preceded by an accompanying opening ( bracket somewhere earlier in the string.

Examples of all valid organisations with $n=3$:

• ((()))
• ()()()
• (())()
• ()(())
• (()())

Examples of invalid organisations with $n=3$:

• ())(()
• )()()(
• (()))(

Input

Input will consist of a single integer $n$, representing the number of open and closed brackets we want to organise

Output

Output should be a single integer, representing the number of unique strings of balanced parenthesis of length $n$. Since this number could be quite large, output the answer modulo $10^9+7$

Constraints

• $1 \leq n \leq 1000$

Example

3

5

10

16796