시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 0 0 0 0.000%

문제

Magister Bajtocki jest najbardziej lubianym nauczycielem wychowania fizycznego w Szkole Podstawowej nr 64 im. Komiwojażera Bajtazara w Bajtocji. Na każdych zajęciach, po przeprowadzeniu krótkiej rozgrzewki, pyta uczniów w jaką grę zespołową chcieliby grać, a następnie pomaga im podzielić się na drużyny.

Podczas zbiórki uczniowie ustawiają się w szereg, numerując się tym samym kolejnymi liczbami od 1 do n. Mgr Bajtocki tworzy drużyny tak, aby każda z nich stanowiła spójny fragment szeregu. Każdy z uczniów musi należeć do jednej z drużyn.

Nauczyciel dobrze zna swoich uczniów i wie, że uczeń o numerze i będzie zadowolony z podziału tylko wtedy, gdy liczba zawodników w jego drużynie będzie nie mniejsza niż ci oraz nie większa niż di.

Mgr Bajtocki zastanawia się, czy da się podzielić uczniów na drużyny tak, aby każdy z nich był zadowolony. Jeśli jest to możliwe, chciałby poznać maksymalną możliwą liczbę powstałych drużyn, a także liczbę podziałów realizujących to maksimum.

입력

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 1 000 000), oznaczająca liczbę uczniów. Kolejne n wierszy opisuje preferencje uczniów: i-ty z tych wierszy zawiera dwie liczby całkowite ci, di (1 ≤ cidin), oznaczające, że uczeń o numerze i będzie zadowolony, gdy liczba zawodników w jego drużynie będzie należała do przedziału [ci, di].

출력

Jeśli da się podzielić uczniów według procedury mgra Bajtockiego tak, aby każdy z nich był zadowolony, na wyjście należy wypisać dwie liczby całkowite oddzielone pojedynczym odstępem - maksymalną liczbę drużyn i liczbę podziałów realizujących to maksimum. Drugą z tych liczb należy wypisać modulo 109 + 7.

Jeśli uczniów nie da się podzielić zgodnie z powyższymi wymogami, na wyjście należy wypisać słowo NIE.

예제 입력 1

9
1 4
2 5
3 4
1 5
1 1
2 5
3 5
1 3
1 1

예제 출력 1

5 2

예제 입력 2

2
1 1
2 2

예제 출력 2

NIE