w Explanation||C++/Python using Math Pascal's triangle/comb Beats 96.74%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first element in array must be the root. Then divide the array into left subtree an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first element in array must be the root. Then divide the array into left subtree and right subtree! \n\nUse recursion, if the subproblems for left subtree and right subtree are solved, with the returning number l and r, Use the following formula:\n$$\nTotalNumber=l\\times r\\times C^{N-1}_{Len(left\\_subtree)}-1\n$$\nto solve the problem! Remember modulo 10**9+7 \n\nPlease turn on the English subtitles if neccessary!\n[https://youtu.be/eS-Po5QJE24](https://youtu.be/eS-Po5QJE24)\n# Why multiplication? The fundamental principle of counting/rule of product or multiplication principle says:\n>  if there are a ways of doing something and b ways of doing another thing, then there are a \xB7 b ways of performing both actions.\n\n# Why the binomial number $C^{N-1}_{Len(left\\_subtree)}$?\nQ: Let N = len(nums). The position for the root is always at index 0. While you can change the positions of elements in the left and right subtrees, you need to maintain the orderings within each subtree. Therefore, there are N-1 available places to position either the left or right subtree. The count of possible arrangements is exactly given by   $C^{N-1}_{Len(left\\_subtree)}$!\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe computation for the binomial number $C^n_k$ from n choose k is using [Pascal\'s triangle](https://leetcode.com/problems/pascals-triangle/solutions/3201092/best-c-solution-via-pascal-s-identity-c-i-j-c-i-i-j-beats-100/)!\n\nThis test case makes using direct method computing  $C^{N-1}_{Len(left\\_subtree)}$ impossible in C++, even using unsigned long long! But in python there is a function comb. \n```\n[74,24,70,11,6,4,59,9,36,82,80,30,46,31,22,34,8,69,32,57,18,21,37,83,55,38,41,72,48,65,27,60,73,58,68,50,16,77,75,20,81,3,61,13,10,29,62,49,12,66,39,45,28,40,42,52,78,56,44,17,14,67,35,26,19,5,63,51,43,23,79,2,54,47,76,53,7,25,64,33,1,15,71]\n```\n![Pascal.png](https://assets.leetcode.com/users/images/0b85189f-ed0d-4b24-af86-7166ff978740_1686921922.1673555.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code with Explanation in comments\n```\nclass Solution {\npublic:\n    long Mod = 1e9 + 7;\n    // Calculate C_{n} choose k using Pascal\'s equation\n    vector<vector<long>> C; // Matrix to store calculated binomial coefficients\n    \n    long compute_C_N_choose_K(int N, int K) {\n        if (K > N / 2)\n            K = N - K; // C_N choose K = C_N choose N-K\n        \n        C.assign(N + 1, vector<long>(K + 1, 0)); \n        // Initialize the matrix with zeros\n        \n        for (int i = 0; i <= N; i++) {\n            C[i][0] = 1; // Set the first column of each row to 1\n            \n            for (int j = 1; j <= min(i, K); j++)\n                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod; \n            // Calculate binomial coefficient using Pascal\'s equation\n        }\n        \n        return C[N][K]; // Return the computed binomial coefficient\n    }\n\n    long Subproblem(vector<int>& nums) {\n        int n = nums.size();\n        \n        if (n <= 2)\n            return 1; \n// Base case: If the number of elements is less than or equal to 2, \n//there is only one way to split\n        \n        vector<int> left, right;\n        int root = nums[0]; // Choose the first element as the root\n        \n        // Split the remaining elements into left and \n        //right parts based on their values compared to the root\n        for (int i = 1; i < n; i++) {\n            if (root < nums[i])\n                right.push_back(nums[i]); \n// Add the element to the right part if it is greater than the root\n\n            else\n                left.push_back(nums[i]); \n// Add the element to the left part if \n//it is less than or equal to the root\n        }\n        \n        long r = Subproblem(right) % Mod; \n// Recursively calculate the number of ways for the right part\n\n        long l = Subproblem(left) % Mod; \n// Recursively calculate the number of ways for the left part\n        \n        return compute_C_N_choose_K(n - 1, left.size()) * r % Mod * l % Mod; \n// Compute the total number of ways based on binomial coefficients \n// and the number of ways for left and right parts\n    }\n\n    int numOfWays(vector<int>& nums) {\n        return Subproblem(nums); \n// Start the recursive computation by calling the Subproblem function\n    }\n};\n\n```\n# 2nd Solution w SC O(N) & twice faster than 1st one\n```\nclass Solution {\npublic:\n    int Mod=1e9+7;\n    //Calcute C_{n} choose k by Pascal\'s equation\n    \n    int compute_C_N_choose_K(int N, int K){\n        if (K>N/2) K=N-K;//C_N choose K =C_N choose N-K\n        vector<int> C_N(K+1, 0), prevC(K+1, 0);\n        for(int i=0; i<=N; i++){\n            C_N[0]=1;\n            for(int j=1; j<=min(i, K);j++){\n                C_N[j]=((long)prevC[j-1]+prevC[j])%Mod;  \n            }\n            prevC=C_N;  \n        }\n        return C_N[K];\n    }\n\n    long Subproblem(vector<int>& nums){\n        int n=nums.size();\n        if (n<=2) return 1;\n        vector<int> left, right;\n        int root=nums[0];\n        for (int i=1; i<n; i++){\n            if (root<nums[i]) right.push_back(nums[i]);\n            else left.push_back(nums[i]);\n        }\n        long r=Subproblem(right), l=Subproblem(left);\n        return compute_C_N_choose_K(n-1, left.size())*r%Mod*l%Mod;\n\n    }\n    int numOfWays(vector<int>& nums) {\n        return (Subproblem(nums)-1)%Mod;\n    }\n};\n```\n# Python solution Runtime 155 ms Beats 96.74%\n```\nclass Solution:   \n    def numOfWays(self, nums: List[int]) -> int:\n        Mod=10**9+7\n        import math\n        def Subproblem(nums: List[int]):\n            n=len(nums)\n            if n<=2: return 1\n            root=nums[0]\n            left=[]\n            right=[]\n            for y in nums[1:]:\n                if y<root: left.append(y)\n                else: right.append(y)\n            return Subproblem(right)*Subproblem(left)%Mod*math.comb(len(nums)-1, len(left))%Mod\n        return int((Subproblem(nums)-1)%Mod)\n```
['Math', 'Divide and Conquer', 'Dynamic Programming', 'C++', 'Python3']