Most Complicated (But faster than 93% users) C++ Approach
Intuition\n Describe your first thoughts on how to solve this problem. \n\nI dare you to find the intuition in this programme.\n\nUsed (dp + divide and conquer 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nI dare you to find the intuition in this programme.\n\nUsed (dp + divide and conquer + combinatorics + Tree + dfs + math).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nExtremely Complicated Approach consisting of making of the BST then\nsolving the problme with the help of divide and conquer approch and to solve for one segment use the the combinatorics with finding all the nCr\'s int only O(n)(for all combined).\n\n\n# Complexity\n- Time complexity: O(nlogn).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> fac;\n    int MOD = 1e9 + 7;\n    long long power(long long a, long long b,int m)\n{\n    if(b == 0) return 1;\n\n    a = a % m;\n    long long temp = power(a, b/2,m);\n    if(b&1)\n        return (((temp * temp) % m) * a) % m;\n    else\n        return (temp * temp) % m;\n}\n\nlong long modInverse(long long n, int p)\n{\n    return power(n, p - 2, p);\n}\nlong long mul(long long x,\n                       long long y, int p)\n{\n    return x * 1ull * y % p;\n}\nlong long divide(long long x,\n                          long long y, int p)\n{\n    return mul(x, modInverse(y, p), p);\n}\n    class bst{\n        public:\n            int val;\n            bst* l;\n            bst* r;\n            bst(int v){\n                val = v;\n                l = NULL;\n                r = NULL;\n            }\n    };\n    pair<int,long long> dfs(bst* root){\n        if(!root) return {0,1};\n        pair<int,long long> a = dfs(root->l);\n        pair<int,long long> b = dfs(root->r);\n        long long ans = divide(fac[a.first+b.first],mul(fac[b.first],fac[a.first],MOD),MOD);\n        ans = mul(ans,a.second,MOD);\n        ans = mul(ans,b.second,MOD);\n        return {(a.first+b.first+1),ans};\n    }\n    int numOfWays(vector<int>& arr) {\n        bst* root = new bst(arr[0]);\n        fac.push_back(1);\n        for(int i = 1;i<arr.size();i++){\n            fac.push_back((fac[i-1]*i)%MOD);\n            int a = arr[i];\n            bst* node = root;\n            bst* t = new bst(a);\n            while(1){\n                if(a > node->val){\n                    if(node->r == NULL){\n                        node->r = t;\n                        break;\n                    }\n                    node = node->r;\n                }\n                else{\n                    if(node->l == NULL){\n                        node->l = t;\n                        break;\n                    }\n                    node = node->l;\n                }\n            }\n        }\n        return (int)(dfs(root).second - 1);\n    }\n};\n```
['Math', 'Divide and Conquer', 'Binary Search Tree', 'Combinatorics', 'C++']