The World Needs Another Python Solution
Approach\n\nWe use recursion. The steps below explain the solution.\n\n1. The root must be inserted first.\n2. The order of nodes inserted in the left subtree i
# Approach\n\nWe use recursion. The steps below explain the solution.\n\n1. The root must be inserted first.\n2. The order of nodes inserted in the left subtree is independent of the order of nodes inserted in the right subtree.\n3. The nodes in the left subtree can be inserted in any order relative to the nodes in the right subtree.\n4. The recursive relationship is therefore \n`f(nums) = f(left subtree nodes list)*f(right subtree nodes list)*C(len(left subtree)+len(right subtree), len(left subtree))`\nwhere C(n, k) is the binomial coefficient, also called "n choose k". In this expression, the product `f(left subtree nodes list)*f(right subtree nodes list)` comes from  observation (2), and the binomial coefficient `C(len(left subtree)+len(right subtree), len(left subtree))` comes from observation (3).\n5. The base case is f([]) == 1.\n6. Since we\'re returning the number of ways of reordering the list, we need to exclude the present ordering. This means we need to subtract 1 from the final result. The need to subtract 1 at the end is also the only reason why we need to define a separate function inside of our function body to perform the recursion. (We don\'t want to subtract 1 on recursive calls.)\n7. Don\'t forget to give the result modulo 10**9 + 7.\n\n# Complexity\n- Time and space complexity are both O(n^2) in the worst case, O(n*log(n)) in the average case.\n- The worst case occurs when the list is mostly sorted.\n\n# Code\n```\nfrom math import comb\n\nB = 10**9 + 7\n\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        def f(nums):\n            if len(nums) == 0:\n                return 1\n            \n            left = [n for n in nums if n < nums[0]]\n            right = [n for n in nums if n > nums[0]]\n\n            return f(left)*f(right)*comb(len(left) + len(right), len(left)) % B\n\n        return (f(nums)-1) % B\n```
['Python3']