Problem Description

During a physical education class, $n$ children are standing in a row, numbered from $1$ to $n$. The teacher wants to divide them into several groups, each containing a consecutive sequence of children, with each child belonging to exactly one group.

The $i$-th child desires that the group they belong to has no more than $d_i$ children and no fewer than $c_i$ children; otherwise, they will be dissatisfied.

Given that all children are satisfied, find the maximum number of groups that can be formed and the number of ways to achieve this maximum number of groups.

Input Format

The first line contains an integer $n$, representing the number of children.

The next $n$ lines each contain two integers $c_i$ and $d_i$, indicating the minimum and maximum number of children in the group the $i$-th child belongs to.

Output Format

If no such arrangement exists, output a single line containing NIE.

Otherwise, output a line with two integers: the maximum number of groups and the number of ways to achieve this maximum, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5 2

Sample Input #2

2
1 1
2 2

Sample Output #2

NIE

Notes/Hints

For $100\%$ of the data, $1 \le n \le 10^6$, and $1 \le c_i \le d_i \le n$.

见题面 Input 部分

见题面 Output 部分