A library files new call numbers into a binary search tree: each number is inserted in arrival
order with the usual rule (smaller goes left, larger goes right, starting from the root). Today's
arrivals were order, a list of distinct integers.
Count how many arrival orders of the same numbers (the given one included) would produce exactly
the same tree (same root, same shape, same number at every position). The answer can be huge,
so return it modulo 10**9 + 7. An empty list builds the empty tree in one way, so return 1.
Examples
Input: order = [3, 1, 4, 2, 5]
Output: 6
Explanation: 3 must come first. After that, 1 must precede 2 and 4 must precede 5,
and the pairs can be interleaved in C(4, 2) = 6 ways.
Input: order = [2, 1, 3]
Output: 2
Explanation: [2, 1, 3] and [2, 3, 1] build the same tree.
Constraints
0 <= len(order) <= 3000, values are distinct integers- Trying every permutation is hopeless even for 15 numbers.
Goals
- See which relative orders an insertion sequence must keep to give the same tree
- Count interleavings of two subtrees with a binomial coefficient
- Compute subtree sizes without deep recursion