Combinations, Modular Inverse using Fermat's Little Theorem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe position for the root is fixed at the first position, the left and the right sub-tr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe position for the root is fixed at the first position, the left and the right sub-trees can be mixed with each other but without changing the order in each sub-tree.\n\nWe can get an initial answer, which is the number of combinations $$C^n_k$$, where $$n$$ is the length of the array and $$k$$ is the number of nodes in either the left sub-tree or the right sub-tree (the result should be the same because $$C^n_k = C^n_{n-k}$$).\n\nFor the order of each sub-tree, we can use a recursive approach and multiplying them into the initial answer we can get the final answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. `inverse`: Get the modular inverse using *Fermat\'s Little Theorem*: $$a^{-1} = a^{M - 2}\\mod M$$\n    - `power`: Get the power efficiently.\n2. `c`: Calculate $$C^n_k$$. Use `inverse` to convert division to multiply so that we can perform the modulo.\n    - `numerator`: The numerator is the product from `n - k + 1` to `n` inclusively.\n    - `denominator`: The denominator is the product from `1` to `k` inclusively.\n\n# Complexity\nComplexity is calculated in average occasions, for dividing into two parts and recursively solve each part.\n\nIn each iteration, we used $$O(n)$$ to get each sub-tree and $$O(n)$$ to calculate the number of combinations (with $$log_2M$$ to get the power), so $$O(n)$$ is the answer.\n\nWe perform recursions based on the input, if the numbers of nodes in the left and right sub-trees are approximetely equal, we can get a recursion depth of $$O(log_2n)$$.\n- Time complexity: $$O(n\\log_2n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n\\log_2n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nconst int mod = 1e9+7;\n\nstatic int power(int x, int y) { return y == 0 ? 1 : (y % 2 == 0 ? power((long)x * x % mod, y / 2) : (long)x * power(x, y - 1) % mod); }\nint inverse(int a) { return power(a, mod - 2); }\n\nstatic int numerator(int i, int n) { return i <= n ? (long)numerator(i + 1, n) * i % mod : 1; }\nstatic int denominator(int i, int k) { return i <= k ? (long)denominator(i + 1, k) * i % mod : 1; }\nint c(int n, int k) { return (long)numerator(n - k + 1, n) * inverse(denominator(1, k)) % mod; }\n\nstatic void count(int i, int n, int *cg, int *cl, int *nums) { i < n ? ((nums[i] > nums[0] ? (*cg)++ : (*cl)++), count(i+1, n, cg, cl, nums)) : (void)0; }\nstatic void subs(int i, int n, int *g, int ig, int *l, int il, int *nums) { i < n ? ((nums[i] > nums[0] ? (g[ig++] = nums[i]) : (l[il++] = nums[i])), subs(i+1, n, g, ig, l, il, nums)) : (void)0; }\nint numOfWays(int *nums, int numsSize)\n{\n    int *g, cg = 0, *l, cl = 0;\n    int ans, i;\n\n    return count(1, numsSize, &cg, &cl, nums),\n        g = (cg > 0 ? calloc(cg, sizeof *g) : NULL),\n        l = (cl > 0 ? calloc(cl, sizeof *l) : NULL),\n        subs(1, numsSize, g, 0, l, 0, nums),\n        ans = (long)c(numsSize-1, cg) * (cg > 2 ? numOfWays(g, cg) + 1 : 1) % mod * (cl > 2 ? numOfWays(l, cl) + 1 : 1) % mod,\n        free(g),\n        free(l),\n        (ans - 1) % mod;\n}   \n```
['C']