Mountain Arrangement Counting

IK is working on terrain modeling. One stage of the work is to arrange several mountains in a row. Each mountain has a unique label, a unique height, and a key number. For every mountain in the arrangement, let \(cnt\) be the number of mountains that appear before it with a height greater than its own. The arrangement is valid if for every mountain, \(cnt < k\) (where \(k\) is the key number of that mountain).

For every valid arrangement, IK produces two sequences: the label sequence (the order of mountain labels) and the contour sequence (the order of mountain heights). Given the information of all mountains, determine the total number of different valid label sequences (and equivalently, contour sequences) that can be obtained.

Note: The mountain information is given as follows. The first line of input contains a single integer \(n\) representing the number of mountains. Each of the following \(n\) lines contains three integers: the label, the height, and the key number of a mountain. It is guaranteed that all labels and heights are distinct.

The condition for a valid arrangement is that for each mountain placed at some position in the sequence, if \(cnt\) denotes the number of mountains before it with height greater than its own, then it must hold that \(cnt < k\), where \(k\) is the key number of that mountain.

inputFormat

The input begins with an integer \(n\) (\(1 \leq n \leq 10\)), representing the number of mountains. The following \(n\) lines each contain three space-separated integers:

• label (unique mountain identifier),
• height (unique mountain height),
• k (the key number for the mountain).

It is guaranteed that all labels and heights are distinct.

outputFormat

Output a single integer: the total number of valid arrangements (i.e. the number of distinct valid label sequences) that satisfy the condition.

sample

2
1 3 1
2 4 1

1