Cartesian tree

Consider a special type of binary search tree known as a "Cartesian tree". In a binary search tree, each node contains a key (an integer in this problem), and for each node (u), the following conditions hold: all keys in the left subtree of (u) are less than the key in (u), and all keys in the right subtree are greater.

A binary search tree is called a Cartesian tree if, in addition to the main key (x_u), each node (u) also has an auxiliary key (y_u), satisfying the "heap condition": if (v) is an ancestor of (u), then (y_v < y_u).

We define a set of pairs ((x_1, y_1), (x_2, y_2), ..., (x_n, y_n)) as correct if all (x_i) are distinct numbers from (1) to (n), and the same condition applies to (y_i). It can be shown that for any correct set of pairs, there is exactly one Cartesian tree that includes these pairs as key pairs.

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) to transform it into a Cartesian tree.

For example, for the tree depicted 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)}).

Input

The first line of the input contains (n) — the number of nodes in the tree (T) ((1 $\le$ n $\le$ 200)). The following (n) lines describe its nodes. Each node is described by two numbers: the indices of the left and right children. If a child is absent, its index is given as (0). It is guaranteed that the tree description is correct. The root of the tree is numbered (1).

Output

Output a single number — the number of different correct sets of pairs that can be arranged in the nodes of (T) to form a Cartesian tree.

Examples