1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)

int c[1000000], d[1000000], b[1000001], w[1000001];
const int MOD = 1000000005, INF = 2000000000;

int main() {
	int n;
	scanf("%d", &n);
	REP(i,n) scanf("%d%d", &c[i], &d[i]);
	REP(i,n+1) b[i] = -1;
	b[0] = 0;
	w[0] = 1;
	REP(i,n) {
		int mi = -INF, ma = INF;
		REP(j,i+1) {
			mi = max(mi, c[i - j]);
			ma = min(ma, d[i - j]);
			if (j + 1 > ma) break;
			if (j + 1 >= mi && b[i - j] >= 0) {
				if (b[i + 1] < b[i - j] + 1) {
					b[i + 1] = b[i - j] + 1;
					w[i + 1] = w[i - j];
				} else if (b[i + 1] == b[i - j] + 1)
					w[i + 1] = (w[i + 1] + w[i - j]) % MOD;
			}
		}
	}
	if (b[n] >= 0) printf("%d %d\n", b[n], w[n]);
	else printf("NIE\n");
}