Hide

# Fiat

The king of Rectangle Land has just received a royal gift, a stairstep-shaped piece of wood with $N$ steps, from the neighboring kingdom of Stairstep-Shaped Piece of Wood With $N$ Steps Land.

The king accepted the gift out of courtesy, but he actually has a disdain for stairstep-shaped pieces of wood with $N$ steps, as it reminds him of the time he fell down the stairs and tore a ligament. He decided to give you, his royal advisor, a royal fiat to divide this stairstep-shaped piece of wood with $N$ steps into more reasonable shapes: rectangles. Figure 1: Illustration of Sample Input 1.

Having solved royal problems before, you were able to do this quickly. You realized that this would make a boring problem, so you decided to make it more interesting. Now, you must calculate how many possible ways there are to divide this stairstep-shaped piece of wood with $N$ steps into $N$ axis-aligned, integer-dimension rectangles.

## Input

The first and only line of input contains an integer $N$ ($1 \leq N \leq 100\, 000$), the number of steps in the stairstep-shaped piece of wood.

## Output

Output a single integer on a line by itself, the number of ways to divide this stairstep-shaped piece of wood with $N$ steps into $N$ rectangles.

Since this number can be quite large, you should output only the remainder after dividing this number by $10^9+7$.

Sample Input 1 Sample Output 1
4

14

Sample Input 2 Sample Output 2
7

429

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.7hard
Statistics Show