Count Alternative Insertion Orders for One BST

### Problem Insert the distinct values of `nums`, a permutation of `1..n`, into an empty binary search tree in their given order. Count other permutations of those values that create the identical BST. Exclude the original permutation and return the count modulo `10^9 + 7`. ```cpp class Solution { public: int numOfWays(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text nums = [2,1,4,3] Output: 2 Explanation: Besides the original, [2,4,1,3] and [2,4,3,1] produce the same tree. ``` **Example 2:** ```text nums = [4,3,2,1] Output: 0 Explanation: Every node must precede its descendant in the left chain, fixing the insertion order. ``` ### Constraints - `1 <= nums.length <= 1000`. - Each value is in `[1, nums.length]`, and all values are distinct. ### Clarifying Questions The root value and the entire left/right structure must match, not merely the inorder traversal. The original ordering is not counted, as established by the source examples. ```hint Inspect the structure Which features of the complete labeled tree must stay unchanged, and which insertion orders must be excluded from the count? ``` ### Reasoning checkpoints - Count all and only the alternative orders that reproduce the full labeled BST. - Avoid counting an ordering twice, and exclude the original with correct modular arithmetic. ### Optional extensions How would duplicate keys require an explicit BST insertion policy?