P1375 Kittens

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).

A single line containing an integer $n$.

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

### 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