## TTOP - Tree Topology

no tags

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: 3Output: 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. m@j!n {Amit Gupta}: 2011-08-22 15:28:51 if the input is 4 and 5 then what will be the output for these values answer: Judging by the correct submissions, the problem is well defined, so you may try finding a solution on paper... Also, I'd suggest finding a solution without figuring out patterns. Last edit: 2010-12-10 16:09:31