Bajtocki 老师是 Bajtocja 市 Bajtazar 旅行商小学最受欢迎的体育老师。每节课在简短的热身运动后，他都会询问学生们想玩什么团队游戏，然后帮助他们分成若干个队伍。

在集合时，学生们排成一列，并按顺序从 $1$ 到 $n$ 进行编号。Bajtocki 老师将学生分成若干个队伍，使得每个队伍都是队列中的一个连续片段。每位学生都必须属于且仅属于一个队伍。

老师非常了解他的学生，他知道编号为 $i$ 的学生只有在所在队伍的人数不小于 $c_i$ 且不大于 $d_i$ 时才会感到满意。

Bajtocki 老师想知道是否可以将学生分成若干个队伍，使得每位学生都感到满意。如果可能的话，他想知道所能形成的队伍的最大数量，以及实现该最大数量的划分方案数。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示学生人数。接下来的 $n$ 行描述了学生的偏好：第 $i$ 行包含两个整数 $c_i, d_i$ ($1 \le c_i \le d_i \le n$)，表示编号为 $i$ 的学生在所在队伍人数处于区间 $[c_i, d_i]$ 时会感到满意。

输出格式

如果可以按照 Bajtocki 老师的要求将学生分组，使得每位学生都感到满意，则输出两个由空格分隔的整数——最大队伍数量以及实现该最大数量的划分方案数。第二个数请对 $10^9 + 7$ 取模。

如果无法按照上述要求进行分组，则输出 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