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).
A single line containing the integer n.
A single integer: the number of distinct binary search trees modulo 1000000007.
Example 1
Input
3
Expected
5
Explanation
With keys 1, 2, 3 there are 5 distinct search-tree shapes, so the answer is 5.
Example 2
Input
1
Expected
1
Explanation
A single key forms exactly one tree.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →