SP8004 TTOP - Tree Topology

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

A single integer N ( 1

A single integer representing the solution modulo 1000000007.