C++ || Recursion + Combinatorics using Pascal table || Great Question
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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\n```\nclass Solution {\npublic:\n    typedef long long int64;\n    vector<vector<int64>> table;\n    const int MOD = (int)1e9 + 7;\n    \n    // ways(nums) = ways(leftNodes) * ways(rightNodes) * (nums.size() - 1)C(leftNodes.size())\n    // (nums.size() - 1)C(leftNodes.size()) = num of ways to keep leftNodes in same order keeping the root\'s position unchanged.\n\n    int64 solve(vector<int> &nums) {\n        int n = nums.size();\n        if(n <= 2) {\n            return 1;\n        }\n        vector<int> leftNodes, rightNodes;\n        for(int i = 1; i < n; i++) {\n            if(nums[i] < nums[0]) {\n                leftNodes.push_back(nums[i]);\n            } else {\n                rightNodes.push_back(nums[i]);\n            }\n        }\n        int64 leftWays = solve(leftNodes) % MOD;\n        int64 rightWays = solve(rightNodes) % MOD;\n        return ((leftWays * rightWays) % MOD) * table[n - 1][leftNodes.size()] % MOD;\n    }\n\n    int numOfWays(vector<int>& nums) {\n        int n = nums.size();\n        table.resize(n + 1); // pascal triangle\n        for(int i = 0; i < (n + 1); i++) {\n            table[i] = vector<int64> (i + 1, 1);\n            for(int j = 1; j < i; j++) {\n                // nCr + nCr-1 = n+1Cr\n                table[i][j] = (table[i - 1][j] + table[i - 1][j - 1]) % MOD;\n            }\n        }\n\n        return (solve(nums) - 1) % MOD;\n    }\n};\n```
['C++']