The Competitive Programming Solution [C++]
This is not a typical DSA solution, and leans more towards CP. Please don\'t downvote -- I already warned you :)\n\n# Approach\n-> Fix the root and then think a
This is not a typical DSA solution, and leans more towards CP. Please don\'t downvote -- I already warned you :)\n\n# Approach\n-> Fix the root and then think about combinations.\n-> Every node has two sides; left and right\n-> At the top most level, we cannot change the order ordering among the left side elements or the right side elements, but we can change the ordering of how a combination of these left side and right side element is present.\n```\n-> For eg: [3,4,5,1,2]\n-> root is 3\n-> Left side: [1,2]\n-> Right side: [4,5]\n-> Now we cant change the ordering among (1 and 2) and (4 and 5)\n-> But we can change between their combination (1,2,4,5), (1,4,2,5), (4,5,1,2) etc.\n```\n\n-> For each node we will see combinations this way i.e. left side and right side.\n-> With some observation you\'ll understand that if the number of elements on the right side is denoted by `l[node]` and right side `r[node]`, there can be a total of \n\n$$\\Large~~~~~~~~~~~~~~~~~{l[node]+r[node]-1 \\choose l[node]} + {l[node]+r[node]-1 \\choose r[node]}$$ \n\n\ncombinations are possible corresponding to this node. \n***[** ASK IF YOU DON\'T UNDERSTAND THIS, I CAN EXPLAIN WITH A DIAGRAM **]***\n\n\n# Complexity\n- Time complexity: O(n^2)\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    unordered_map<int,int> l;\n    unordered_map<int,int> r;\n\nint modMul(int a, int b,int mod)\n{\n    int res = 0; \n \n    a %= mod;\n \n    while (b) {\n        if (b & 1)\n            res = (res + a) % mod;\n \n        a = (2 * a) % mod;\n \n        b >>= 1; \n    }\n \n    return res;\n}\n \n\n    int power(int x, int y, int p)\n{\n    int res = 1;\n \n    x = x % p; \n \n    while (y > 0)\n    {\n     \n        if (y & 1)\n            res = modMul(res,x,p);\n \n        y = y >> 1; \n        x = modMul(x, x, p);\n    }\n    return res;\n}\n \nint modInverse(int n, int p)\n{\n    return power(n, p - 2, p);\n}\n \n\nint nCr(int n, int r, int p)\n{\n    if (n < r)\n        return 0;\n    if (r == 0)\n        return 1;\n \n\n    int fac[n + 1];\n    fac[0] = 1;\n    for (int i = 1; i <= n; i++)\n        fac[i] = modMul(fac[i - 1],i,p);\n \n    return modMul(modMul(fac[n],modInverse(fac[r], p),p),modInverse(fac[n - r], p),p);\n}\n\n    void createBST(vector<vector<int>>& v, int root, int num){\n        if(num<root){\n            l[root]++;\n            if(v[root][0]==0){\n                v[root][0]=num;\n            }\n            else createBST(v,v[root][0],num);\n        }\n        else{\n            r[root]++;\n            if(v[root][1]==0){\n                v[root][1]=num;\n            }\n            else createBST(v,v[root][1],num);\n        }\n    }\n    int numOfWays(vector<int>& nums) {\n        // l.clear();\n        // r.clear();\n        vector<vector<int>> v(nums.size()+1, vector<int>(2,0));\n        for(int i = 1; i<nums.size(); i++){\n            createBST(v,nums[0],nums[i]);\n        }\n        int count = 1;\n        int mod = 1e9+7;\n        for(int i = 1; i<nums.size()+1; i++){\n            if((l[i]!=0)&&(r[i]!=0))count = modMul(count,(nCr(l[i]+r[i]-1,l[i],1e9+7)+nCr(l[i]+r[i]-1,r[i],1e9+7))%(mod),mod);\n        }\n        return count-1;\n    }\n};\n```
['Math', 'Divide and Conquer', 'Combinatorics', 'C++']