Consider binary search trees that store the keys 1, 2, ..., n (each key used once, obeying the search-tree ordering: every key in a node's left subtree is smaller and every key in its right subtree is larger). Two trees are the same only if they have the identical shape and the identical key at every node.
Count the number of structurally distinct such trees, modulo 1000000007. For n = 0 there is one tree (the empty tree).
Input format
A single line containing the integer n.
Output format
A single integer: the number of distinct binary search trees modulo 1000000007.
Constraints
- 0 <= n <= 1000