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.

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

4 |
14 |

Sample Input 2 | Sample Output 2 |
---|---|

7 |
429 |