题目描述

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

输入格式

第一行一个整数n(1<=n<=1000000)，表示小朋友的数目。 接下来n行，每行两个整数c[i],di，表示i所在组的人数的最小值和最大值。

输出格式

如果不存在这样的方案，仅输出一行NIE。 否则输出一行包含两个整数，组的数目的最大值、方案数量。（方案数量对1000000007取模）

9
1 4
2 5
3 4
1 5
1 1
2 5
3 5
1 3
1 1
样例输入2：
2
1 1
2 2

5 2
样例输出2：
NIE

提示

没有写明提示

题目来源

鸣谢Jcvb