Mr Byteotish is the most popular P.E. teacher at No. 64 Primary School named after Byteasar, the Travelling Salesman of Byteotia. During each lesson, after a brief warm-up, he ask students to choose the team game they would like to play, and then helps them to get divided into teams.
During the line-up the students number themselves up using consecutive numbers from $1$ to $n$. Mr Byteotish creates the teams in such a way that each of them is formed from students with consecutive numbers. Each student must belong to one of the teams.
The teacher knows his students well and knows that the student number $i$ will be satisfied with his assignation only in case the number of the players in his team will not be less than $c_i$ and not exceed $d_i$.
Mr Byteotish wonders whether it is possible to divide students into teams in such a way, that every student would be satisfied. In case it is possible, he would like to know the maximum possible number of teams that could be formed, as well as the number of divisions that are pursuing this maximum.
Input
The first line of input contains one integer $n$ $1\leq n \leq 1\,000\,000$), denoting the number of students. The following $n$ lines describe the preferences of students: $i$-th of these lines contains two integers $c_i, d_i$ ($1\leq c_i\leq d_i\leq n$), indicating that the student bearing number $i$ is satisfied, providing the number of players in his team will belong to the interval $[c_i,d_i]$.
Output
In case it is possible to divide students according to Mr Byteotish's procedure in such a way, that each of them would be satisfied, the output should contain two integers separated by a single space---the maximum number of teams and number of divisions pursuing this maximum. The second of these numbers should be produced modulo $10^9+7$.
If students cannot be divided in accordance with the above requirements, output should contain only the word \texttt{NIE} (Polish for \emph{no}).
Examples
Input
9 1 4 2 5 3 4 1 5 1 1 2 5 3 5 1 3 1 1
Output
5 2
Input
2 1 1 2 2
Output
NIE