[PA2014] Druzyny

题目描述

体育课上，$n$ 个小朋友排成一行（从 $1$ 到 $n$ 编号），老师想把他们分成若干组，每一组都包含编号连续的一段小朋友，每个小朋友属于且仅属于一个组。

第 $i$ 个小朋友希望它所在的组的人数不多于 $d_i$，不少于 $c_i$，否则他就会不满意。

在所有小朋友都满意的前提下，求可以分成的组的数目的最大值，以及有多少种分组方案能达到最大值。

输入格式

第一行一个整数 $n$，表示小朋友的数目。

接下来 $n$ 行，每行两个整数 $c_i,d_i$，表示 $i$ 所在组的人数的最小值和最大值。

输出格式

如果不存在这样的方案，仅输出一行 NIE。

否则输出一行包含两个整数，组的数目的最大值、方案数量。（方案数量对 $10^9+7$ 取模）

样例 #1

样例输入 #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

2
1 1
2 2

样例输出 #2

NIE

提示

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le c_i\le d_i\le n$。