detailed explanation - Java simple recursive divide and conquer solution
PLEASE UPVOTE IF THE SOLUTION WAS USEFUL !!\n\n\nThere are different steps in order to come up with this solution:\n1.  logic\n2.  maths formula(permutation and
***PLEASE UPVOTE IF THE SOLUTION WAS USEFUL !!***\n\n\nThere are different steps in order to come up with this solution:\n1.  logic\n2.  maths formula(permutation and combination)\n3.  algorithm - divide and conquer\n4.  optimisation(space) - modular inverse\n5.  optimisation(time) - moduler exponentiation\n\nI will explain the first 3 steps : \n\n**Logic**\nConsider base case for array  ``` 5 1 3 2 4 7 9 8 6```\n-> 5 would be the root\n-> ```1 3 2 4 ``` say ```A``` are less than 5 and ```7 9 8 7 ```  say ```B``` are greater than 5\n-> at this point you can say that  ```A``` will always be to left of ```5``` and ```B``` will always be to the right in the constructed binary tree.\n->So, relative positions of ```A``` and ```B``` dont matter. (don\'t mix elements within A and within B yet, we will solve this as a part of sub problems)\n-> how many ways can you mix in ```A``` and ```B``` so that relative positions within their respective sub arrays remains the same ?\n\n**Math Formula**\n-> size of ```A``` is ```na``` and ```B``` is ```nb``` respectively.\n-> You can look up for ```Identical objects into distinct bins``` on google and relate it to this question. \n-> Numbers in ```A``` can be considered as identical since you cannot permute amongst themselves\n-> There are ```nb + 1```  distinct bins because ```na``` identical nums can be in any of these ```nb+1``` distinct bins. (.ie. say ```B``` is ```1 2 3``` , there are ```4``` places where you can keep other numbers from ```A```)\n->The formula for such a senario is ```Suppose there are n identical objects to be distributed among r distinct bins. This can be done in precisely (n+r-1) C (r-1) ways.```\n\n***Algorithm***\n\n--> We have solved only for the case considering the root. Now, all you need to do is figure out how many ways with which ```A``` and ```B``` can be permuted independently and multiply everything.\n--> ```(na+nb+1-1) C (nb+1-1) * ans for A * ans for B```\n\n\n```\nclass Solution {\n    \n    private static long mod = 1000000007;\n    private long[] inverse = new long[10001];\n    \n    public int numOfWays(int[] nums) {\n        inverseFunc();\n        \n        List<Integer> list =new ArrayList<>();\n        for(int n : nums){\n            list.add(n);\n        }\n        return (int)((num(list)-1)%mod);\n    }\n    \n    public long num(List<Integer> nums){\n        \n        if(nums == null || nums.size() <= 2) return 1;\n        \n        \n        int root = nums.get(0);\n        List<Integer> lessThan = new ArrayList<>();\n        List<Integer> greaterThan = new ArrayList<>();\n        \n        for(int val : nums){\n            if(val > root){\n                greaterThan.add(val);\n            } else if(val < root){\n                lessThan.add(val);\n            }\n        }\n        \n        return ((((comb(lessThan.size() + greaterThan.size(), greaterThan.size()))%mod) * num(lessThan))%mod * num(greaterThan))%mod;\n    }\n    \n    \n    public long comb(int a, int b){\n        if(a <= 0 || b <= 0) return 1;\n        \n        long ans = 1;\n        for(int i = 1; i<=b;i++){\n            ans = (ans * a)%mod;\n            a--;\n        }\n        \n        while(b>=1){\n            ans = (ans * inverse[b--])%mod;\n        }\n        return ans;\n    }\n    \n    \n    \nvoid inverseFunc(){\n    for(int i = 1; i<= 1000;i++){\n        inverse[i] = power(i, mod-2, mod)%mod;\n    }\n}    \n    \n    \nlong power(long x, long y, long p){\n    long res = 1;\n \n    x = x % p; \n \n    if (x == 0)\n      return 0;\n \n    while (y > 0)\n    {\n \n      if ((y & 1) != 0)\n        res = (res * x) % p;\n \n      y = y >> 1;\n      x = (x * x) % p;\n    }\n    return res;\n  }\n    \n}\n```
['Divide and Conquer', 'Java']