시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB43819011244.094%

문제

N개의 식물이 표면에 떠 있는 호수에 코끼리 한 마리가 살고 있다. 이 호수는 각각의 식물들이 정수 좌표에 있는 좌표평면으로 나타낼 수 있다.

매일 아침마다 이 코끼리는 식물들 위를 신나게 뛰어다니며 아침 운동을 한다. 왜 그런지는 모르겠지만 이 코끼리는 항상 현재 식물보다 x, y좌표가 둘 다 큰 식물로만 뛸 수 있다. 다시 말해서, (x1, y1)에 있는 식물로부터 x2 > x1이고 y2 > y1일때만 코끼리는 (x2, y2)로 뛸 수 있다. 이 코끼리는 호수 위의 아무 식물에서나 운동을 시작할 수 있다.

모든 식물의 좌표가 주어졌을때, 코끼리가 최대로 뛸 수 있는 식물의 개수를 계산하시오. 그리고 그렇게 뛸 수 있는 방법의 수를 계산하시오. 이때 이 방법의 수가 너무 클 수 있기 때문에 1 000 000 007로 나눈 나머지를 출력하시오.

입력

첫 번째 줄에는 식물의 수 N(1 ≤ N ≤ 300 000)이 들어온다.

이후 N개의 줄에는 각각의 식물의 좌표 xi, yi(0 ≤ xi, yi ≤ 1 000 000 000)가 들어온다. (단, 두 식물이 같은 좌표에 있는 경우는 없다.)

출력

첫 번째 줄에는 코끼리가 최대로 뛸 수 있는 식물의 개수를 출력하시오.

두 번째 줄에는 그렇게 뛸 수 있는 방법의 수를 1 000 000 007로 나눈 값을 출력하시오.

예제 입력 1

4
1 1
4 2
2 3
3 4

예제 출력 1

3
1

예제 입력 2

6
1 3
2 2
3 1
5 3
4 4
3 5

예제 출력 2

2
7

예제 입력 3

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

예제 출력 3

4
3
W3sicHJvYmxlbV9pZCI6IjMxMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWIwN2NcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVjMmRkXHViYjNjXHVjNzc0IFx1ZDQ1Y1x1YmE3NFx1YzVkMCBcdWI1YTAgXHVjNzg4XHViMjk0IFx1ZDYzOFx1YzIxOFx1YzVkMCBcdWNmNTRcdWIwN2NcdWI5YWMgXHVkNTVjIFx1YjljOFx1YjlhY1x1YWMwMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNjM4XHVjMjE4XHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGRcdWJiM2NcdWI0ZTRcdWM3NzQgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTRcdWM3N2MgXHVjNTQ0XHVjZTY4XHViOWM4XHViMmU0IFx1Yzc3NCBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgXHVjMmRkXHViYjNjXHViNGU0IFx1YzcwNFx1Yjk3YyBcdWMyZTBcdWIwOThcdWFjOGMgXHViNmYwXHVjNWI0XHViMmU0XHViMmM4XHViYTcwIFx1YzU0NFx1Y2U2OCBcdWM2YjRcdWIzZDlcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM2NWMgXHVhZGY4XHViN2YwXHVjOWMwXHViMjk0IFx1YmFhOFx1Yjk3NFx1YWNhMFx1YzljMFx1YjljYyBcdWM3NzQgXHVjZjU0XHViMDdjXHViOWFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ2MDRcdWM3YWMgXHVjMmRkXHViYjNjXHViY2Y0XHViMmU0IHgsIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHViNDU4IFx1YjJlNCBcdWQwNzAgXHVjMmRkXHViYjNjXHViODVjXHViOWNjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0XHVjMTFjLCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmRkXHViYjNjXHViODVjXHViZDgwXHVkMTMwIHg8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj5cdWM3NzRcdWFjZTAgeTxzdWI+MjxcL3N1Yj4gJmd0OyB5PHN1Yj4xPFwvc3ViPlx1Yzc3Y1x1YjU0Y1x1YjljYyBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPilcdWI4NWMgXHViNmY4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgXHVkNjM4XHVjMjE4IFx1YzcwNFx1Yzc1OCBcdWM1NDRcdWJiMzQgXHVjMmRkXHViYjNjXHVjNWQwXHVjMTFjXHViMDk4IFx1YzZiNFx1YjNkOVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0XHViNTRjLCBcdWNmNTRcdWIwN2NcdWI5YWNcdWFjMDAgXHVjZDVjXHViMzAwXHViODVjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViODA3XHVhYzhjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWFjMDAgXHViMTA4XHViYjM0IFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCAxIDAwMCAwMDAgMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRkXHViYjNjXHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMzAwIDAwMClcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWM4OGNcdWQ0NWMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwKVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIChcdWIyZTgsIFx1YjQ1MCBcdWMyZGRcdWJiM2NcdWM3NzQgXHVhYzE5XHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZjU0XHViMDdjXHViOWFjXHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI2ZjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyZGRcdWJiM2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViODA3XHVhYzhjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSAwMDAgMDAwIDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0xPTiIsImRlc2NyaXB0aW9uIjoiPHA+QW4gZWxlcGhhbnQgbGl2ZXMgYnkgYSBsYWtlIHdpdGggTiBwbGFudHMgb24gdGhlIHN1cmZhY2UuIFRoZSBsYWtlIGNhbiBiZSBtb2RlbGVkIGJ5IGEgY29vcmRpbmF0ZSBwbGFuZSwgd2l0aCBwbGFudHMgYXQgcG9pbnRzIHdpdGggaW50ZWdlciBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgbW9ybmluZyBhZnRlciB3YWtpbmcgdXAsIHRoZSBlbGVwaGFudCBwZXJmb3JtcyBoaXMgbW9ybmluZyBleGVyY2lzZSwgaGFwcGlseSBqdW1waW5nIGZyb20gcGxhbnQgdG8gcGxhbnQuIEZvciByZWFzb25zIGJlc3QgbGVmdCB1bmRpc2N1c3NlZCwgdGhlIGVsZXBoYW50IGNhbiBhbHdheXMganVtcCBvbmx5IHRvIGFub3RoZXIgcGxhbnQgd2l0aCBib3RoIGNvb3JkaW5hdGVzIGxhcmdlciB0aGFuIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcGxhbnQgaXQgaXMgY3VycmVudGx5IG9uLiBJbiBvdGhlciB3b3JkcywgZnJvbSBwbGFudCAoeDEsIHkxKSB0aGUgZWxlcGhhbnQgY2FuIGp1bXAgdG8gcGxhbnQgKHgyLCB5Mikgb25seSBpZiB4MiAmZ3Q7IHgxIGFuZCB5MiAmZ3Q7IHkxLiBUaGUgZWxlcGhhbnQgY2FuIHN0YXJ0IGhpcyBleGVyY2lzZSBhdCBhbnkgcGxhbnQgb24gdGhlIGxha2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgY29vcmRpbmF0ZXMgb2YgYWxsIHBsYW50cywgY2FsY3VsYXRlcyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHNlcXVlbmNlIG9mIHBsYW50cyB0aGUgZWxlcGhhbnQgY2FuIHZpc2l0LiBBZGRpdGlvbmFsbHksIGNhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzdWNoIGxvbmdlc3Qgc2VxdWVuY2VzLiBCZWNhdXNlIHRoaXMgc2Vjb25kIG51bWJlciBjYW4gYmUgbGFyZ2UsIGNhbGN1bGF0ZSBpdCBtb2R1bG8gMTAwMDAwMDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMzAwMDAwKSwgdGhlIG51bWJlciBvZiBwbGFudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRoZSBjb29yZGluYXRlcyBvZiBvbmUgcGxhbnQsIHR3byBpbnRlZ2VycyBiZXR3ZWVuIDAgYW5kIDEwPHN1cD45PFwvc3VwPi4gTm8gdHdvIHBsYW50cyB3aWxsIGhhdmUgdGhlIHNhbWUgcGFpciBvZiBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvdXRwdXQgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzZXF1ZW5jZSBvZiBwbGFudHMgdGhlIGVsZXBoYW50IGNhbiBqdW1wIG9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGxpbmUgb3V0cHV0IHRoZSBudW1iZXIgb2Ygc3VjaCBzZXF1ZW5jZXMgb2YgbWF4aW11bSBsZW5ndGgsIG1vZHVsbyAxMDAwMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2008 > National Competition #2 - Seniors 3번

  • 데이터를 추가한 사람: cgiosy
  • 문제를 번역한 사람: luke0201