Statistics

In this problem we consider the simplest possible binary search trees (BSTs).

(When looking for an element in a BST, you start by comparing it to the root. If you are looking for a smaller element, you recursively search for it in the left subtree, and if you are looking for a bigger element, you do the same with the right subtree.

When inserting a new element into a BST, you follow the same path as when looking for it and then you insert it at the place where your unsuccessful search terminated.)

When searching for an element X in a BST, the time complexity is clearly proportional to the number of BST nodes we have to compare to X.

A BST is called worst-case optimal if it minimizes the maximum number of comparisons.

A BST is called average-case optimal if it minimizes the expected number of comparisons under the assumption that X is one of the elements present in the BST, picked uniformly at random.

A BST is called only WC optimal if it is worst-case optimal but not average-case optimal.

A BST is called only AC optimal if it is average-case optimal but not worst-case optimal.

Each permutation of numbers 0 to N-1 determines a binary search tree as follows: we start with an empty BST and we insert the 0 to N-1 in the order given by the permutation.

Note that different permutations may produce the same BST. For example, both the permutation {2, 1, 0, 3} and {2, 1, 3, 0} produce the BST shown below. (Node 2 is the root of that BST.)

    2
   / \
  1   3
 /
0

For the BST above the maximum number of comparisons is 3 (when looking for element 0) and the expected number of comparisons is exactly 2 (the average of 3, 2, 1, and 2). For N = 4 this BST is both worst-case and average-case optimal.

Given N, let:

• OWC be the number of permutations of 0 to N-1 that determine a BST that is only WC optimal.
• OAC be the number of permutations of 0 to N-1 that determine a BST that is only AC optimal.

Return a int[] with two values: { OWC modulo (10^9 + 7), OAC modulo (10^9 + 7) }.