Number of Ways to Reorder Array to Get Same BST solution and explanation

MOD = 10**9 + 7

def numOfWays(nums):
    from math import comb
    
    def count(nums):
        if len(nums) <= 2:
            return 1
        
        root = nums[0]
        left = [x for x in nums if x < root]
        right = [x for x in nums if x > root]
        left_count = count(left)
        right_count = count(right)
        return comb(len(left) + len(right), len(left)) * left_count * right_count % MOD
    
    return (count(nums) - 1) % MOD

import java.util.*;

public class Solution {
    private static final int MOD = (int)1e9 + 7;
    
    public int numOfWays(int[] nums) {
        return (int)(helper(nums) - 1);
    }

    private long helper(int[] nums) {
        if (nums.length <= 2) {
            return 1;
        }
        int root = nums[0];
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int num : nums) {
            if (num < root) {
                left.add(num);
            } else if (num > root) {
                right.add(num);
            }
        }
        long leftWays = helper(left.stream().mapToInt(i -> i).toArray());
        long rightWays = helper(right.stream().mapToInt(i -> i).toArray());
        long comb = comb(left.size() + right.size(), left.size());
        return (comb * leftWays % MOD) * rightWays % MOD;
    }

    private long comb(int n, int k) {
        long res = 1;
        for (int i = 0; i < k; ++i) {
            res = res * (n - i) / (i + 1);
        }
        return res % MOD;
    }
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
    static const int MOD = 1e9 + 7;
    vector<vector<int>> comb;

    int dfs(vector<int>& nums) {
        if (nums.size() <= 2) return 1;
        int root = nums[0];
        vector<int> left, right;
        for (int num : nums) {
            if (num < root) left.push_back(num);
            if (num > root) right.push_back(num);
        }
        long leftWays = dfs(left);
        long rightWays = dfs(right);
        return ((combs(left.size() + right.size(), left.size()) * leftWays % MOD) * rightWays) % MOD;
    }

    int combs(int n, int k) {
        if (comb[n][k] != -1) return comb[n][k];
        if (k == 0 || k == n) return 1;
        return comb[n][k] = (combs(n - 1, k - 1) + combs(n - 1, k)) % MOD;
    }

public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        comb.resize(n + 1, vector<int>(n + 1, -1));
        return dfs(nums) - 1;
    }
};

using System;
using System.Collections.Generic;

public class Solution {
    private const int MOD = 1000000007;
    private int[][] dp;

    public int NumOfWays(int[] nums) {
        int n = nums.Length;
        dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return (helper(nums) - 1); // -1 to exclude original ordering
    }

    private int Comb(int n, int k) {
        if (k == 0 || k == n) return 1;
        if (dp[n][k] != -1) return dp[n][k];
        return dp[n][k] = (Comb(n - 1, k - 1) + Comb(n - 1, k)) % MOD;
    }

    private int helper(int[] nums) {
        if (nums.Length <= 2) return 1;
        int root = nums[0];
        var left = new List<int>();
        var right = new List<int>();
        foreach (var num in nums) {
            if (num < root) left.Add(num);
            else if (num > root) right.Add(num);
        }
        int leftWays = helper(left.ToArray());
        int rightWays = helper(right.ToArray());
        return (int)((Comb(left.Count + right.Count, left.Count) * (long)leftWays % MOD) * (long)rightWays % MOD);
    }
}

function numOfWays(nums: number[]): number {
    const n = nums.length;
    const mod = 1e9 + 7;
    const c = new Array(n).fill(0).map(() => new Array(n).fill(0));
    c[0][0] = 1;
    for (let i = 1; i < n; ++i) {
        c[i][0] = 1;
        for (let j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    const dfs = (nums: number[]): number => {
        if (nums.length < 2) {
            return 1;
        }
        const left: number[] = [];
        const right: number[] = [];
        for (let i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[0]) {
                left.push(nums[i]);
            } else {
                right.push(nums[i]);
            }
        }
        const m = left.length;
        const n = right.length;
        const a = dfs(left);
        const b = dfs(right);
        return Number((BigInt(c[m + n][m]) * BigInt(a) * BigInt(b)) % BigInt(mod));
    };
    return (dfs(nums) - 1 + mod) % mod;
}

func numOfWays(nums []int) int {
	n := len(nums)
	const mod = 1e9 + 7
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
	}
	c[0][0] = 1
	for i := 1; i < n; i++ {
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
		}
	}
	var dfs func(nums []int) int
	dfs = func(nums []int) int {
		if len(nums) < 2 {
			return 1
		}
		var left, right []int
		for _, x := range nums[1:] {
			if x < nums[0] {
				left = append(left, x)
			} else {
				right = append(right, x)
			}
		}
		m, n := len(left), len(right)
		a, b := dfs(left), dfs(right)
		return c[m+n][m] * a % mod * b % mod
	}
	return (dfs(nums) - 1 + mod) % mod
}