Unique lake

Interview

Time limit1sMemory limit1024 MB

Summary

Find the length of the longest chain of points where each next point is strictly greater in both x and y, and count such longest chains modulo 1e9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Segment tree
Solved: No attempts yet

Problem

Slon Mirko lives beside a large lake with $n$ lily pads. Think of the lake as a coordinate plane, where each lily pad sits at a point with integer coordinates.

Every morning Mirko does his exercise by hopping from pad to pad. For reasons known only to him, he can jump from one pad only to a pad whose both coordinates are greater than the coordinates of the current pad. In other words, Mirko can jump from the pad at $(x_1, y_1)$ to the pad at $(x_2, y_2)$ only if $x_2 > x_1$ and $y_2 > y_1$ . Mirko chooses the first pad himself.

Mirko wants the exercise to last as long as possible, and he wants to jump in a different way each day.

For the given layout of lily pads, find the length of the longest sequence of pads that satisfies Mirko's conditions. Also find the number of such longest sequences. Since this number can be very large, output only its remainder modulo $1\,000\,000\,007$ .

Input

The first line contains the natural number $n$ ( $1 \le n \le 300\,000$ ) from the statement.

Each of the next $n$ lines contains two non-negative integers $x$ and $y$ ( $0 \le x, y \le 10^9$ ), the coordinates of one lily pad.

No two lily pads are at the same coordinates.

Output

On the first line, print the length of the longest sequence of lily pads that Mirko can jump across, as described in the statement.

On the second line, print the remainder of the number of different longest sequences when divided by $1\,000\,000\,007$ .

Examples3

Example 1
Input
```
4
1 1
4 2
2 3
3 4
```
Expected output
```
3
1
```
Example 2
Input
```
6
1 3
2 2
3 1
5 3
4 4
3 5
```
Expected output
```
2
7
```

Example 3

Input

Expected output

4
3