“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.
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.
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 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|
|Sample Input 2||Sample Output 2|