[PA2014] Druzyny

题目描述

体育课上,$n$ 个小朋友排成一行(从 $1$ 到 $n$ 编号),老师想把他们分成若干组,每一组都包含编号连续的一段小朋友,每个小朋友属于且仅属于一个组。 第 $i$ 个小朋友希望它所在的组的人数不多于 $d_i$,不少于 $c_i$,否则他就会不满意。 在所有小朋友都满意的前提下,求可以分成的组的数目的最大值,以及有多少种分组方案能达到最大值。

输入输出格式

输入格式


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

输出格式


如果不存在这样的方案,仅输出一行 `NIE`。 否则输出一行包含两个整数,组的数目的最大值、方案数量。(方案数量对 $10^9+7$ 取模)

输入输出样例

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

说明

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