2 Easiest C++ Solution🔥 || DP🔥 || Fastest 🔥🔥🔥
\n# Approach : Dynamic Programming\n Describe your approach to solving the problem. \n\n# Code 1\n\nclass Solution {\n    vector<vector<long long int>> dp;\n   
\n# Approach : Dynamic Programming\n<!-- Describe your approach to solving the problem. -->\n\n# Code 1\n```\nclass Solution {\n    vector<vector<long long int>> dp;\n    long long MOD = 1e9 + 7;\n\n    unsigned long long solve(vector<int> &nums) {\n        if (nums.size() <= 1) return 1;\n        vector<int> l, r;\n        for (int i = 1; i < nums.size(); ++i) {\n            if (nums[i] > nums[0]) r.push_back(nums[i]);\n            else l.push_back(nums[i]);\n        }\n        int n = l.size(), m = r.size();\n        return solve(l) * solve(r) % MOD * dp[n + m][n] % MOD;\n    }\n\npublic:\n    int numOfWays(vector<int> &nums) {\n        dp = vector<vector<long long>>(nums.size() + 1, vector<long long>(nums.size() + 1, 0));\n        for (int i = 1; i < nums.size() + 1; ++i) {\n            dp[i][0] = 1;\n            dp[i][1] = i;\n            dp[i][i - 1] = i;\n            dp[i][i] = 1;\n        }\n        for (int i = 2; i < nums.size() + 1; ++i) {\n            for (int j = 2; j < nums.size() + 1; ++j) {\n                if (i >= j) dp[i][j] = (dp[i - 1][j - 1] % MOD + dp[i - 1][j] % MOD) % MOD;\n                else break;\n            }\n        }\n        return solve(nums) - 1;\n    }\n};\n```\n\n\n# Approach : Pascal Triangle\n<!-- Describe your approach to solving the problem. -->\n\n# Code 2\n```\nclass Solution {\npublic:\n    vector < vector < long long > > pascal;\n    int MOD = 1e9 + 7;\n    \n    int numOfWays(vector<int>& nums) {\n        int N = nums.size();\n        pascal = vector < vector < long long > > (N + 1);\n        for (int i = 0; i < N + 1; i ++){\n            pascal[i] = vector < long long > (i + 1, 1);\n            for (int j = 1; j < i; j ++){\n                pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1])%MOD;\n            }\n        }\n        return dfs(nums) - 1;\n    }\n    \n    int dfs(vector < int > nums){\n        if (nums.size() <= 2)\n            return 1;\n        vector < int > left, right;\n        for (int i = 1; i < int(nums.size()); i ++){\n            if (nums[i] < nums[0])\n                left.push_back(nums[i]);\n            else\n                right.push_back(nums[i]);\n        }\n        return (((dfs(left) * pascal[nums.size() - 1][left.size()]) % MOD) * dfs(right))%MOD;\n    }\n};\n```
['Divide and Conquer', 'Dynamic Programming', 'Combinatorics', 'C++']