Building a Binary Search Tree

A Binary Search Tree (BST) is a rooted binary tree with the following properties:

• The left subtree contains only nodes with values strictly less than the value at the root.

• The right subtree contains only nodes with values strictly greater than the value at the root.

• All node values are distinct.

• The left and right subtrees are also recursively binary search trees.

When inserting a new node, the following algorithm is used:

1. If the tree is empty, the new node becomes the root and the insertion process ends. Otherwise, proceed to step $2$.

2. Set the root of the tree as the current node.

3. If the value of the new node is less than the current node:

   • If the left subtree of the current node is empty, the new node becomes the left child of the current node and the algorithm ends.

   • Otherwise, set the current node to the root of the left subtree and return to step $3$.

4. If the value of the new node is greater than the current node:

   • If the right subtree of the current node is empty, the new node becomes the right child of the current node and the algorithm ends.

   • Otherwise, set the current node to the root of the right subtree and return to step $3$.

The BST structure depends on the input sequence. Different sequences may produce different structures, even if the numbers themselves are the same.

Consider the sequence $1$ $2$ $3$. We obtain the following BST:

If the input sequence is $2$ $1$ $3$, we obtain the tree:

On the other hand, different inputs can yield the same BST structure. For example, the sequence $2$ $1$ $3$ will create the same BST structure as the sequence $4$ $6$ $2$. The tree will be:

Given $n$ nodes of a BST, determine how many different input sequences produce the same BST structure as the given one. The node values are taken from the range $1\dots m$.