MCONVOI - Con Voi

no tags 

An elephant lives by a lake with N plants on the surface. The lake can be modeled by a coordinate plane, with plants at points with integer coordinates. Every morning after waking up, the elephant performs his morning exercise, happily jumping from plant to plant. For reasons best left undiscussed, the elephant can always jump only to another plant with both coordinates larger than the coordinates of the plant it is currently on. In other words, from plant (x1, y1) the elephant can jump to plant (x2, y2) only if x2 > x1 and y2 > y1. The elephant can start his exercise at any plant on the lake. Write a program that, given the coordinates of all plants, calculates the length of the longest sequence of plants the elephant can visit. Additionally, calculate the number of different such longest sequences. Because this second number can be large, calculate it modulo 1 000 000 007.

Input

The first line contains the integer N (1 ≤ N ≤ 300 000), the number of plants. Each of the following N lines contains the coordinates of one plant, two integers between 0 and 10^9. No two plants will have the same pair of coordinates.

Output

On the first line output the length of the longest sequence of plants the elephant can jump on. On the second line output the number of such sequences of maximum length, modulo 1 000 000 007.

Sample

input 
11
8 6
7 4
5 4
5 1
5 6
6 2
3 2
4 3
4 5
3 5
2 4
output
4
3
input 
6
1 3
2 2
3 1
5 3
4 4
3 5
output
2
7



Added by:psetter
Date:2009-03-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 08