Description

Recently, IK has been working on terrain modeling. One stage of the work is to arrange several mountains in a line. Each mountain has a unique label and a height. To satisfy certain design requirements, each mountain is assigned a key number, requiring that for each mountain, the number of other mountains that are higher than it and placed before it must be less than its key number. Obviously, there can be many permutations that satisfy this requirement.

For every possible permutation, IK generates a corresponding label sequence and a height sequence. The label sequence is obtained by writing down the labels of the mountains in order.

The height sequence is obtained by writing down their heights in order. For example, if there are two mountains, and in one valid permutation the first mountain has label and height $1$ and $3$, and the second mountain has label and height $2$ and $4$, then the label sequence of this permutation is $1$ $2$, and the height sequence is $3$ $4$.

Now, given all the information about the mountains, IK wants to know how many different valid label sequences and height sequences there are in total.

Input Format

The first line contains the number of mountains $N$. The next $N$ lines each contain two integers. In the order of labels from $1$ to $N$, they give the height and the key number of each mountain.

Output Format

Output two space-separated numbers. The first is the number of distinct label sequences, and the second is the number of distinct height sequences. Both answers should be taken modulo $2011$, that is, output the remainders of the two answers divided by $2011$.

2
1 2
2 2

2 2

Hint

Constraints: For all testdata, $1 \leq N \leq 1000$, and all numbers are positive integers not exceeding $10^9$.

Translated by ChatGPT 5