Given a rooted tree, a permutation of its nodes is valid if the following holds: for each pair of nodes a and b, if a is an ancestor of b, then a appears before b in the permutation. Let P(t) be the number of valid permutations for a tree t.

Given an integer N, you can construct all the possible trees of N nodes, numbered from 1 to N, rooted at 1. I'd like to know what's the sum of P(t) for all t that can be constructed for the given N.

We consider two trees equal iff each node in the second tree has the same parent as it does in the first one. 

The picture shows all the possible trees for N = 3.

Input

A single integer N ( 1 <= N <= 1000000 ).

Output

A single integer representing the solution modulo 1000000007.

Example

Input: 
3
Output: 
4

Explanation: If you take a look at the picture, you'll see that the first two trees have one valid permutation each, and the third tree has two, namely { 1, 2, 3 } and { 1, 3, 2 }. The total is, of course, 4.