There are many fun things to do in preparation for Christmas. Some decorate Christmas trees, others bake gingerbread cookies, and computer scientists like Nella build graphs. In particular, Nella starts off with a collection of $N$ nodes. Then, for each node, she chooses one of the other nodes uniformly at random and connects the two nodes with an undirected edge. Note that it is possible for there to be more than one edge between a pair of nodes.

Nella does not want her graph to be too disconnected or it would be too much of a hassle to clean up. Therefore, as her older sibling, you should help her determine the expected number of connected components in her graph.

Constraints

$2\le N\le {10}^6$

Subtask 1 [5%]

$2\le N\le 8$

Subtask 2 [35%]

$2\le N\le 3\times {10}^3$

Subtask 3 [60%]

No additional constraints.

Input Specification

The first and only line contains an integer $N$, the number of nodes in Nella's graph.

Output Specification

Output $P{Q}^{-1}mod{10}^9+7$, where the expected number of connected components in Nella's graph can be expressed as a fraction ${\displaystyle \frac{P}{Q}}$ in lowest terms, and $Q^{-1}$ is an integer such that $Q{Q}^{-1}\equiv 1(\mathrm{mod}{10}^9+7)$.

Sample Input

4

Sample Output

370370374

Explanation

Out of all $81$ possibilities, $78$ of them form a graph with $1$ connected component and $3$ of them form a graph with $2$ connected components. So, the expected number of connected components is ${\displaystyle \frac{78}{81}}\times 1+{\displaystyle \frac{3}{81}}\times 2={\displaystyle \frac{28}{27}}$.