Easy C++ solution (It's mainly about nCr)
I have calculated nCr using binary exponentiation and Class 12th nCr formula and Modular multiplicative inverse.\n\n```\nnCr= n! / r!(n-r)!\n\nclass Solution {\
I have calculated nCr using binary exponentiation and Class 12th nCr formula and Modular multiplicative inverse.\n\n```\nnCr= n! / r!*(n-r)!\n\nclass Solution {\npublic:\n    long long fac[1001];\n    int mod=1e9+7;\n    void fact() {     // To calculate the Factorial and mod for value in range\n        fac[0]=1;\n        for(int i=1;i<=1000;i++) {\n            fac[i]=1LL*fac[i-1]*i;\n            fac[i]%=mod;\n        }\n    }\n    long long bin(long long n, long long m) {   //Binary Exponentiaition (log n calculation)\n        long long ans=1;\n        while(m) {\n            if(m&1) {\n                ans*=n; ans%=mod;\n            }\n            n*=n; n%=mod;\n            m/=2;\n        }\n        return ans;\n    }\n    long long ncr(int n, int k) {   // Calculating nCr using the above formula\n        long long ans=fac[n];\n        long long den=1LL*fac[k]*fac[n-k]%mod;\n        return 1LL*(ans%mod*bin(den, mod-2)%mod)%mod;   \n    }\n    long long dfs(vector<int>&nums) {\n        int n=nums.size();\n        if(n<3) return 1;\n        vector<int> left, right;\n        for(int i=1;i<n;i++) if(nums[i]<nums[0]) left.push_back(nums[i]);\n        else right.push_back(nums[i]);\n        long long l1=dfs(left);\n        long long r1=dfs(right);\n        return 1LL*ncr(n-1, left.size())%mod*l1%mod*r1%mod;\n    }\n    int numOfWays(vector<int>& nums) {\n        fact();\n        return (int) dfs(nums)-1;\n    }\n};
['Divide and Conquer', 'C']