Cartesian tree

Consider a special kind of binary search tree called a Cartesian tree. In a binary search tree, each node contains a key (an integer in this problem), and for every node $u$, the following conditions must hold: all keys in the left subtree of $u$ are less than the key at $u$, and all keys in the right subtree are greater than the key at $u$.

A binary search tree is called a Cartesian tree if, in addition to the main key x_u, each node $u$ also stores an auxiliary key y_u, such that the following heap condition is satisfied: if $v$ is an ancestor of $u$, then y_v < y_u.

We call a set of pairs (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) correct if all x_i are distinct numbers from $1$ to $n$, and the same condition holds for y_i. For any correct set of pairs, there exists exactly one Cartesian tree in which the nodes contain exactly these key pairs.

You are given a binary tree $T$ with $n$ nodes. Your task is to determine the number of different correct sets of pairs that can be assigned to the nodes of $T$ so that $T$ becomes a Cartesian tree.

For example, for the tree shown in the figure, there are three corresponding correct sets of pairs:

\{(1, 2), (2, 3), (3, 1), (4, 4)\}, \{(1, 2), (2, 4), (3, 1), (4, 3)\}, and \{(1, 3), (2, 4), (3, 1), (4, 2)\}.