MCONVOI - Con Voi

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mconvoi


Nhằm mục đích giới thiệu các bạn CON VOI!

Mỗi sáng dậy, voi tập thể dục giảm béo bằng cách nhảy cao. Nó nhảy từ ô (x1, y1) đến ô (x2, y2) với x2 > x1 và y2 > y1. Nó có thể bắt đầu nhảy từ một một vị trí bất kỳ. Tính số bước nhảy tối đa theo quy tắc trên và số cách nhảy khác nhau mà có cùng số bước nhảy tối đa, kết quả là phần dư chia cho 1000000007.

Input

Dòng đầu là số vị trí N (1 ≤ N ≤ 300 000), N dòng tiếp theo là tọa độ các vị trí, 0 <=xi,yi<=10^9. Không có 2 tọa độ trùng nhau.

Output

Dòng 1: số bước nhảy nhiều nhất theo quy tắc trên.
Dòng 2: số cách nhảy , lấy dư theo module 1000000007.

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

Note: Task SLON - COI 08! Biết cách làm bài này thì có thể làm được thêm 4 bài khác nữa!!!! Solution trên mạng!


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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.