Question
Non intersecting paths
In a vibrant kingdom, a clever architect named "Elysia" was given 2*N enchanted stones arranged in a line. Her task was to design N non-intersecting bridges connecting these stones in pairs, creating a beautiful network. Elysia wanted to know how many unique ways she could construct these bridges without any of them overlapping. She needed to calculate this number while keeping her results within the magical limit of 109 + 7, a safeguard against overwhelming magic.
Can you assist Elysia in determining the total number of distinct arrangements to build the bridges between the enchanted stones?
Input
The first line of the input contains a single integer N.
Constraints
1 ≤ N ≤ 104
Constraints
1 ≤ N ≤ 104
Output
You have to print the number of distinct arrangements in which bridges can be built between the enchanted stones.
Example
Sample Input
2
Sample Output
2
Explanation
If stones are numbered 1 to 4, the different ways to construct the bridges are:
{(1-2), (3-4)} and {(1-4), (2-3)}
2
Sample Output
2
Explanation
If stones are numbered 1 to 4, the different ways to construct the bridges are:
{(1-2), (3-4)} and {(1-4), (2-3)}