Problem F
Fiat

“Your wish is my command.” ­–Genie (Aladdin).

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

4

14

7

429