Go 22ms Solution
Approach\nRecursive function (compute): This function divides the given array into two sub-arrays (namely \'smaller\' and \'larger\') based on the first element
# Approach\nRecursive function (compute): This function divides the given array into two sub-arrays (namely \'smaller\' and \'larger\') based on the first element, simulating the creation of a BST. If there is only one or no element left, it simply returns 1 (base case of recursion). It then recursively calculates the number of ways for both the \'smaller\' and \'larger\' sub-arrays and multiplies them together. Lastly, it multiplies the result by the number of ways to choose the elements for the sub-arrays (calculated by the choose function), which gives the total number of ways to reorder the given array.\n\nChoosing function (choose): This function calculates the number of ways to choose k elements from n elements (i.e., binomial coefficient). It does this using the [multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) method, which is a common way to handle large factorials while avoiding overflow. Here, the multiplicative inverse is calculated using the ModInverse function from the math/big package in Go.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ Each call to compute triggers $$O(n)$$ calls to itself.and this could happen up to n times \n\n- Space complexity:\n$$O(n)$$ as there would be $$n$$ recursive calls.\n\n# Code\n```\nconst mod = 1e9 + 7\nvar cache = make([][]int, 1001)\n\nfunc init() {\n    for i := range cache {\n        cache[i] = make([]int, 1001)\n    }\n}\n\nfunc numOfWays(nums []int) int {\n    return compute(nums) - 1\n}\n\nfunc compute(nums []int) int {\n    if len(nums) <= 1 {\n        return 1\n    }\n\n    smaller, larger := splitNums(nums)\n\n    n := len(nums) - 1\n    k := len(larger)\n    \n    kn := choose(n, k)\n    small := compute(smaller) % mod\n    large := compute(larger) % mod\n\n    res := ((small * large % mod) * kn) % mod\n    return res\n}\n\nfunc splitNums(nums []int) (smaller, larger []int) {\n    for _, x := range nums[1:] {\n        if x > nums[0] {\n            larger = append(larger, x)\n        }\n        if x < nums[0] {\n            smaller = append(smaller, x)\n        }\n    }\n    return smaller, larger\n}\n\nfunc choose(n, k int) int {\n    if k == 0 || k == n {\n        return 1\n    }\n    if cache[n][k] != 0 {\n        return cache[n][k]\n    }\n\n    a, b := 1, 1\n\n    for x := n; x > k; x-- {\n        a = (a * x) % mod\n    }\n    for x := n - k; x > 1; x-- {\n        b = (b * x) % mod\n    }\n\n    inv := big.NewInt(int64(b)).ModInverse(big.NewInt(int64(b)), big.NewInt(int64(mod)))\n    modinv := inv.Int64()\n\n    cache[n][k] = (a * int(modinv)) % mod\n    return cache[n][k]\n}\n\n```
['Go']