C++ | Dynamic Programming | Divide and Conquer | Combinational | Easy to Understand | <100ms
\nclass Solution {\npublic:\nconst long long mod = 1e9+7;\nvector<long long>fact;\nvoid calcFact(){\n    fact[0] =1;\n    fact[1] =1;\n    for(long long i=2;i<1
```\nclass Solution {\npublic:\nconst long long mod = 1e9+7;\nvector<long long>fact;\nvoid calcFact(){\n    fact[0] =1;\n    fact[1] =1;\n    for(long long i=2;i<1001;i++)\n    fact[i] = (fact[i-1]*i)%mod;\n}\n\nlong long modInv(long long n,long long p){\n    if(p==0)\n    return 1LL;\n    long long ans = modInv(n,p/2);\n    if(p&1)\n    return (((ans*ans)%mod)*n)%mod;\n    else\n    return (ans*ans)%mod;\n}\n\nlong long help(vector<int>&nums){\n    if(nums.size()<=2)\n    return 1LL;\n    vector<int>small,large;\n    for(int i=1;i<nums.size();i++){\n        if(nums[i]>nums[0])\n        large.push_back(nums[i]);\n        else\n        small.push_back(nums[i]);\n    }\n    long long ans =1;\n    ans = (ans*fact[(int)nums.size()-1])%mod;\n    ans =(ans*modInv(fact[(int)nums.size()-(int)small.size()-1],mod-2))%mod;\n    ans = (ans*modInv(fact[(int)small.size()],mod-2))%mod;\n    ans = (ans*help(small))%mod;\n    ans = (ans*help(large))%mod;\n    return ans;\n}\n    int numOfWays(vector<int>& nums) {\n        fact = vector<long long>(1001);\n        calcFact();\n        long long ans = help(nums);\n        ans--;\n        ans = (ans+mod)%mod;\n        return ans;\n    }\n};\n```
['Divide and Conquer', 'Dynamic Programming', 'C', 'C++']