The root never moves. Whatever `nums[0]` is, it has to come first in every valid reordering, and then every value below it falls into the left subtree and every value above it into the right, each keeping the relative order it had in the original array. The subtrees' internal orders are frozen. The only thing I get to choose is how the two blocks interleave. That collapses the problem into a binomial coefficient. With `L` elements going left and `R` going right, there are `C(L+R, L)` ways to interleave them, and each subtree contributes its own count the same way. Multiply down the tree, then subtract one for the arrangement I was handed. My first instinct was to enumerate permutations and compare the resulting tree shapes. The array goes up to 1000 elements, so that dies on arrival, and it also hides the actual structure: the tree is given, not chosen. Nothing here is a Catalan-number count over shapes. ## Worked example Take `[3,1,2,5,4,6]`. Root `3`, left block `[1,2]`, right block `[5,4,6]`. Five elements after the root with two of them on the left, so `C(5,2) = 10` interleavings. Left `[1,2]` has size 2, which admits exactly one order. Right `[5,4,6]`: root `5`, left `[4]`, right `[6]`, so `C(2,1) = 2`. `10 * 1 * 2 = 20` arrangements that rebuild this exact tree, and `20 - 1 = 19` once I drop the original. ## Complexity - **Time** `O(n^2)` because the Pascal table costs `n^2` and the partitioning sums to `O(n * depth)`, which degrades to `n^2` on a chain-shaped tree. - **Space** `O(n^2)` from that same binomial table; `1001 x 1001` entries of `long long` is roughly 8 MB. ## Code (C++) ```cpp class Solution { public: static const long long MOD = 1000000007LL; vector> C; long long ways(vector& a) { int n = a.size(); if (n <= 2) return 1; vector left, right; for (int i = 1; i < n; ++i) { if (a[i] < a[0]) left.push_back(a[i]); else right.push_back(a[i]); } long long res = C[n - 1][left.size()]; res = res * ways(left) % MOD; res = res * ways(right) % MOD; return res; } int numOfWays(vector& nums) { int n = nums.size(); C.assign(n + 1, vector(n + 1, 0)); for (int i = 0; i <= n; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } return (int)((ways(nums) - 1 + MOD) % MOD); } }; ``` ## One note The final `-1` is the line to be careful with. `ways()` returns a product of binomials already reduced modulo `1e9+7`, so it can legitimately come back as `0`, and in modular arithmetic `0 - 1` is `MOD - 1`, not `-1`. That is why the return is `(ways(nums) - 1 + MOD) % MOD` and not a bare subtraction. Two more specifics. The base case returns `1` for `n <= 2`, never `0`: a lone node, or a root with a single child, has exactly one insertion order, and a `0` there would wipe out the entire product above it. And the accumulator has to be `long long`, since two factors just under `1e9+7` multiply to about `1e18`, which a signed 64-bit integer holds comfortably and an `int` loses on the first step. LeetCode tags this one with Fermat's Little Theorem, which points toward factorials plus modular inverses. At `n <= 1000` I would skip all of it. Pascal's triangle is a single `O(n^2)` loop of additions with no inverses, no `pow`, and nothing subtle left to get wrong.