시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 56 18 10 27.778%

문제

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

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

예제 출력 1

2
7
W3sicHJvYmxlbV9pZCI6IjMxMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWIwN2NcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVjMmRkXHViYjNjXHVjNzc0IFx1ZDQ1Y1x1YmE3NFx1YzVkMCBcdWI1YTAgXHVjNzg4XHViMjk0IFx1ZDYzOFx1YzIxOFx1YzVkMCBcdWNmNTRcdWIwN2NcdWI5YWMgXHVkNTVjIFx1YjljOFx1YjlhY1x1YWMwMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNjM4XHVjMjE4XHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGRcdWJiM2NcdWI0ZTRcdWM3NzQgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTRcdWM3N2MgXHVjNTQ0XHVjZTY4XHViOWM4XHViMmU0IFx1Yzc3NCBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgXHVjMmRkXHViYjNjXHViNGU0IFx1YzcwNFx1Yjk3YyBcdWMyZTBcdWIwOThcdWFjOGMgXHViNmYwXHVjNWI0XHViMmU0XHViMmM4XHViYTcwIFx1YzU0NFx1Y2U2OCBcdWM2YjRcdWIzZDlcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM2NWMgXHVhZGY4XHViN2YwXHVjOWMwXHViMjk0IFx1YmFhOFx1Yjk3NFx1YWNhMFx1YzljMFx1YjljYyBcdWM3NzQgXHVjZjU0XHViMDdjXHViOWFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ2MDRcdWM3YWMgXHVjMmRkXHViYjNjXHViY2Y0XHViMmU0IHgsIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHViNDU4IFx1YjJlNCBcdWQwNzAgXHVjMmRkXHViYjNjXHViODVjXHViOWNjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0XHVjMTFjLCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmRkXHViYjNjXHViODVjXHViZDgwXHVkMTMwIHg8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj5cdWM3NzRcdWFjZTAgeTxzdWI+MjxcL3N1Yj4gJmd0OyB5PHN1Yj4xPFwvc3ViPlx1Yzc3Y1x1YjU0Y1x1YjljYyBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPilcdWI4NWMgXHViNmY4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWNmNTRcdWIwN2NcdWI5YWNcdWIyOTQgXHVkNjM4XHVjMjE4IFx1YzcwNFx1Yzc1OCBcdWM1NDRcdWJiMzQgXHVjMmRkXHViYjNjXHVjNWQwXHVjMTFjXHViMDk4IFx1YzZiNFx1YjNkOVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0XHViNTRjLCBcdWNmNTRcdWIwN2NcdWI5YWNcdWFjMDAgXHVjZDVjXHViMzAwXHViODVjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViODA3XHVhYzhjIFx1YjZmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzQgXHViNTRjIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjEwOFx1YmIzNCBcdWQwNzQgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMSAwMDAgMDAwIDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDMwMCAwMDApXHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjODhjXHVkNDVjIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPigwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMClcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiAoXHViMmU4LCBcdWI0NTAgXHVjMmRkXHViYjNjXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2Y1NFx1YjA3Y1x1YjlhY1x1YWMwMCBcdWNkNWNcdWIzMDBcdWI4NWMgXHViNmY4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMmRkXHViYjNjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjgwN1x1YWM4YyBcdWI2ZjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEgMDAwIDAwMCAwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNMT04iLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGVsZXBoYW50IGxpdmVzIGJ5IGEgbGFrZSB3aXRoIE4gcGxhbnRzIG9uIHRoZSBzdXJmYWNlLiBUaGUgbGFrZSBjYW4gYmUgbW9kZWxlZCBieSBhIGNvb3JkaW5hdGUgcGxhbmUsIHdpdGggcGxhbnRzIGF0IHBvaW50cyB3aXRoIGludGVnZXIgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IG1vcm5pbmcgYWZ0ZXIgd2FraW5nIHVwLCB0aGUgZWxlcGhhbnQgcGVyZm9ybXMgaGlzIG1vcm5pbmcgZXhlcmNpc2UsIGhhcHBpbHkganVtcGluZyBmcm9tIHBsYW50IHRvIHBsYW50LiBGb3IgcmVhc29ucyBiZXN0IGxlZnQgdW5kaXNjdXNzZWQsIHRoZSBlbGVwaGFudCBjYW4gYWx3YXlzIGp1bXAgb25seSB0byBhbm90aGVyIHBsYW50IHdpdGggYm90aCBjb29yZGluYXRlcyBsYXJnZXIgdGhhbiB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBsYW50IGl0IGlzIGN1cnJlbnRseSBvbi4gSW4gb3RoZXIgd29yZHMsIGZyb20gcGxhbnQgKHgxLCB5MSkgdGhlIGVsZXBoYW50IGNhbiBqdW1wIHRvIHBsYW50ICh4MiwgeTIpIG9ubHkgaWYgeDIgJmd0OyB4MSBhbmQgeTIgJmd0OyB5MS4gVGhlIGVsZXBoYW50IGNhbiBzdGFydCBoaXMgZXhlcmNpc2UgYXQgYW55IHBsYW50IG9uIHRoZSBsYWtlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGNvb3JkaW5hdGVzIG9mIGFsbCBwbGFudHMsIGNhbGN1bGF0ZXMgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzZXF1ZW5jZSBvZiBwbGFudHMgdGhlIGVsZXBoYW50IGNhbiB2aXNpdC4gQWRkaXRpb25hbGx5LCBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc3VjaCBsb25nZXN0IHNlcXVlbmNlcy4gQmVjYXVzZSB0aGlzIHNlY29uZCBudW1iZXIgY2FuIGJlIGxhcmdlLCBjYWxjdWxhdGUgaXQgbW9kdWxvIDEwMDAwMDAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMDAwMCksIHRoZSBudW1iZXIgb2YgcGxhbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIHBsYW50LCB0d28gaW50ZWdlcnMgYmV0d2VlbiAwIGFuZCAxMDxzdXA+OTxcL3N1cD4uIE5vIHR3byBwbGFudHMgd2lsbCBoYXZlIHRoZSBzYW1lIHBhaXIgb2YgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb3V0cHV0IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc2VxdWVuY2Ugb2YgcGxhbnRzIHRoZSBlbGVwaGFudCBjYW4ganVtcCBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lIG91dHB1dCB0aGUgbnVtYmVyIG9mIHN1Y2ggc2VxdWVuY2VzIG9mIG1heGltdW0gbGVuZ3RoLCBtb2R1bG8gMTAwMDAwMCAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d