Combinations + DFS | C++
\nclass Solution {\n    int mod = 1e9 + 7;\n    long dfs(vector<int> &nums, vector<vector<int>> &ncr) {\n        int n = nums.size();\n        if(n <= 2) return
```\nclass Solution {\n    int mod = 1e9 + 7;\n    long dfs(vector<int> &nums, vector<vector<int>> &ncr) {\n        int n = nums.size();\n        if(n <= 2) return 1;\n\n        vector<int> l, r;\n        for(int i=1; i<n; i++) {\n            if(nums[i] < nums[0]) l.push_back(nums[i]);\n            else r.push_back(nums[i]);\n        }\n\n        long left = dfs(l, ncr) % mod;\n        long right = dfs(r, ncr) % mod;\n\n        return ((ncr[n - 1][l.size()] * left) % mod * right) % mod;\n    }\npublic:\n    int numOfWays(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> ncr(n + 1, vector<int>(n + 1, 1));\n\n        for(int i=1; i<=n; i++) {\n            for(int j=1; j<i; j++) {\n                ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % mod;\n            }\n        }\n        \n        return (dfs(nums, ncr) - 1) % mod;\n    }\n};\n\n\n```
['Recursion', 'Combinatorics', 'C++']