유일한 호수
면접 대비시간 제한1초메모리 제한1024 MB
x와 y가 모두 더 큰 점으로만 이동하는 가장 긴 점 순서의 길이와, 그런 가장 긴 순서의 개수를 10^9+7로 나눈 나머지로 구합니다.
문제
슬론 미르코는 연잎 개가 떠 있는 큰 호수 옆에 산다. 호수를 좌표평면으로 생각하면, 각 연잎은 정수 좌표를 가진 점에 놓여 있다.
미르코는 매일 아침 연잎에서 연잎으로 뛰며 운동을 한다. 이유는 본인만 알고 있지만, 미르코는 현재 연잎에서 두 좌표가 모두 현재 연잎의 좌표보다 큰 연잎으로만 뛸 수 있다. 즉 연잎에서 연잎으로 뛸 수 있는 조건은 이고 인 경우뿐이다. 첫 연잎은 미르코가 직접 고른다.
미르코는 운동이 가능한 한 오래 이어지기를 바라고, 매일 다른 방식으로 뛰고 싶어 한다.
주어진 연잎 배치에서 미르코의 조건을 만족하는 연잎 순서 중 가장 긴 것의 길이를 구하라. 또한 그러한 가장 긴 순서의 개수도 구해야 한다. 개수가 매우 클 수 있으므로 로 나눈 나머지만 출력한다.
입력
첫 줄에 문제문의 자연수 ()이 주어진다.
이어지는 개의 줄에는 각각 연잎 하나의 좌표를 나타내는 두 정수 와 ()가 주어진다.
서로 다른 두 연잎이 같은 좌표에 놓이지 않는다.
출력
첫 줄에 문제에서 설명한 대로 미르코가 뛸 수 있는 연잎 순서 중 가장 긴 것의 길이를 출력한다.
둘째 줄에는 가장 긴 순서의 개수를 로 나눈 나머지를 출력한다.