Labelled graphs

Let the number of vertices in a graph be $n$. Compute the number of labelled graphs with $n$ vertices (labelled means that the vertices are marked with the numbers from $1$ to $n$). The edges of the graphs are considered undirected, and loops and multiple edges are forbidden.

Input

The number of vertices $n(1\le n\le 10^5)$ in the graph.

Output

Print the number of labelled graphs with $n$ vertices. Print the answer modulo $10^9+7$.

Examples