<p>Given an array <code>nums</code> that represents a permutation of integers from <code>1</code> to <code>n</code>. We are going to construct a binary search tree (BST) by inserting the elements of <code>nums</code> in order into an initially empty BST. Find the number of different ways to reorder <code>nums</code> so that the constructed BST is identical to that formed from the original array <code>nums</code>.</p>

<ul>
	<li>For example, given <code>nums = [2,1,3]</code>, we will have 2 as the root, 1 as a left child, and 3 as a right child. The array <code>[2,3,1]</code> also yields the same BST but <code>[3,2,1]</code> yields a different BST.</li>
</ul>

<p>Return <em>the number of ways to reorder</em> <code>nums</code> <em>such that the BST formed is identical to the original BST formed from</em> <code>nums</code>.</p>

<p>Since the answer may be very large, <strong>return it modulo </strong><code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/12/bb.png" style="width: 121px; height: 101px;" />
<pre>
<strong>Input:</strong> nums = [2,1,3]
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/12/ex1.png" style="width: 241px; height: 161px;" />
<pre>
<strong>Input:</strong> nums = [3,4,5,1,2]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/12/ex4.png" style="width: 121px; height: 161px;" />
<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no other orderings of nums that will yield the same BST.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>
	<li>All integers in <code>nums</code> are <strong>distinct</strong>.</li>
</ul>

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        mod = 1000000007
        n = len(nums)


        # stores the length of each range of numbers, respectively.
        leng = [0]*(n+2) 

        # stores the count of each range of numbers, respectively.
        cnt = [1]*(n+2) 

        # Iterate the array in reverse order
        for p in nums[::-1]: 
            # k consecutive values larger than p (on the left) are already in BST if leng[p+1] > 0 indicates that. Length [p+1] and h are the respective integers in the right child BST of p.
            h,k = leng[p-1],leng[p+1] 

            # The size of the BST rooted at p should be used to update the lengths at the rightmost and leftmost numbers in the BST (consecutive intervals). Because it won't be needed in the subsequent computation of length and cnt, the numbers in between (p-h, p+k) don't need to be updated.
            leng[p-h]=leng[p+k]=h+k+1 

            # The number of permutated arrays that can construct the BST of the left child and the right child of p is given by dp(BST rooted at p) = dp(left(p-1))*dp(right(p+1))*C(left+right,right).
            t = (cnt[p-1]*cnt[p+1]%mod)*comb(h+k,h)%mod 

            # Only the cnt's rightmost and leftmost elements should be updated because those two numbers will be the only ones used in the next merge interval.
            cnt[p-h]=cnt[p+k]=t 

            # return the number of ways to reorder nums
        return (cnt[1]-1)%mod           
16800