Teams

Mr. Bajtocki is the most popular physical education teacher at Travelling Salesman Bajtazar Primary School No. 64 in Byteotia. In every lesson, after a short warm up, he asks the students which team game they want to play and then helps them split into teams.

At the roll call the students stand in one row and take the numbers $1$ to $n$ in that order. Mr. Bajtocki forms the teams so that every team is a contiguous block of the row. Each student belongs to exactly one team.

The teacher knows his students well, so he knows that student $i$ is happy with the split only if the number of players in that student's team is at least $c_i$ and at most $d_i$.

Decide whether the students can be split so that every student is happy. If they can, find the maximum possible number of teams and the number of splits that reach this maximum.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of students.

Each of the next $n$ lines describes one student. The $i$-th of these lines contains two integers $c_i$ and $d_i$ ($1 \le c_i \le d_i \le n$). Student $i$ is happy when the size of that student's team lies in the range $[c_i, d_i]$.

If the students can be split so that every student is happy, print two integers separated by a single space. The first is the maximum number of teams, the second is the number of splits that reach this maximum, taken modulo $10^9+7$.

If no such split exists, print NIE.