Description

There are $2n$ kittens standing in a circle. Their owner, Xiao Ming, wants to tie their tails together in pairs with strings. At the same time, Xiao Ming is a perfectionist and does not allow any two strings to cross. How many ways are there to connect them so that all kittens are paired?

The number of ways can be large; you only need to output the value modulo $10^9+7$ (a prime).

Input Format

A single line containing an integer $n$.

Output Format

Output the number of ways modulo $10^9+7$.

3

5

Hint

Constraints

• For 60% of the testdata, $1 \le n \le 100$.
• For 100% of the testdata, $1 \le n \le 10^5$.

Translated by ChatGPT 5