Background

Czyzoiers all want to know why Xiao x is so fond of egg pancakes. After some questioning, Xiao x revealed the truth: because he likes circles.

Problem Description

Recently, Xiao x discovered another interesting problem about circles: there are $2N$ distinct points on a circle. Xiao x wants to connect these points with $N$ line segments (each point can be connected by exactly one segment), such that all segments do not intersect. He wants to know how many such connection schemes there are.

The answer is taken modulo $10^8+7$.

Input Format

A single line containing a positive integer $N$ ($1 \le N \le 2999$).

Output Format

A single line containing an integer representing the answer.

The answer is taken modulo $10^8+7$.

24

4057031

Hint

Translated by ChatGPT 5