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
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define f first
#define s second

const int INF = 1000000005;
const int X = 1000000007;
const int size = 1000005;

pair<int, int> T[size];
int n, R[size], M[size];

int main() {
	scanf("%d", &n);
	for(int i = 1; i<=n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		T[i] = make_pair(a, b);
	}
	R[0] = 0;
	M[0] = 1;
	for(int i = 1; i<=n; i++) {
		int r = -INF, m = 0, c = T[i].f, d = T[i].s, counter = 1;
		for(int j = i-1; j>=0; j--) {
			if(counter >= c && counter <= d) {
				if(R[j] > r) {
					r = R[j];
					m = M[j];
				} else if(R[j] == r) {
					m = (m+M[j])%X;
				}
			}
			counter++;
			c = max(c, T[j].f);
			d = min(d, T[j].s);
			if(counter>d) break;
		}
		R[i] = r+1;
		M[i] = m;
	}
	//for(int i = 0; i<n; i++) printf("%d %d\n", R[i], M[i]);
	if(R[n] < 0) printf("NIE\n");
	else printf("%d %d\n", R[n], M[n]);
	return 0;
}