题目描述

题目译自 PA 2014 Runda 3 Drużyny

Bajtocki 老师是拜托西亚拜塔扎尔旅行商人命名的第 64 小学中最受欢迎的体育老师。在每节课上，进行短暂热身后，他会询问学生们想玩哪种团队游戏，然后帮助他们分成团队。

在集合时，学生们排成一列，依次编号为从 $1$ 到 $n$。Bajtocki 老师将学生分成团队，使得每个团队都是队列中的连续片段。每个学生必须属于一个团队。

老师非常了解他的学生，他知道编号为 $i$ 的学生只有在团队人数不少于 $c_{i}$ 且不多于 $d_{i}$ 时才会对分组感到满意。

Bajtocki 老师想知道是否可以将学生分成团队，使得每个学生都感到满意。如果可能，他还想知道可以形成的最大团队数量，以及实现这一最大数量的分组方案数量。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示学生数量。

接下来的 $n$ 行描述学生的偏好：第 $i$ 行包含两个整数 $c_{i}, d_{i}$ $(1 \leq c_{i} \leq d_{i} \leq n)$，表示编号为 $i$ 的学生在团队人数属于区间 $[c_{i}, d_{i}]$ 时会感到满意。

输出格式

如果可以按照 Bajtocki 老师的程序将学生分组，使得每个学生都感到满意，则输出两行，用单个空格分隔的两个整数——最大团队数量和实现这一最大数量的分组方案数量。第二个数字需取模 $10^{9}+7$ 输出。

如果无法按照上述要求分组学生，则输出 NIE。

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

5 2

2
1 1
2 2

NIE