🏆C++ || Recursion || (IMP nCr)
Code\n\nclass Solution {\npublic:\n    vector<vector<long long>>ncr;\n    long long mod=1e9+7;\n    long long ways(vector<int>&v,int n){\n        if(n<=2)return
# Code\n```\nclass Solution {\npublic:\n    vector<vector<long long>>ncr;\n    long long mod=1e9+7;\n    long long ways(vector<int>&v,int n){\n        if(n<=2)return 1;\n        vector<int>left,right;\n        for(int i=1;i<n;i++){\n            if(v[0]>v[i])left.push_back(v[i]);\n            else right.push_back(v[i]);\n        }\n        long long ans_left=ways(left,left.size());\n        long long ans_right=ways(right,right.size());\n\n        long long ans = (((ncr[n-1][left.size()]*ans_left)%mod)*ans_right)%mod;\n        return ans;\n    }\n    int numOfWays(vector<int>& v) {\n        int n=v.size();\n        ncr.resize(n + 1);\n         for(int i = 0; i < n + 1; ++i){\n        ncr[i] = vector<long long>(i + 1, 1);\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 (ways(v,n)-1)%mod;\n    }\n};\n```\n![upvote (2).jpg](https://assets.leetcode.com/users/images/eb696ebe-1bf3-432f-84ff-8bea0433995b_1686894294.3087947.jpeg)\n
['Math', 'Tree', 'Recursion', 'Combinatorics', 'C++']