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
#include<iostream>
#include<vector>

#define VECUINT std::vector<unsigned int>
#define PUII std::pair<unsigned int, unsigned int>
#define VECPUII std::vector<PUII >
const unsigned int INF = 1000000007;

int main(){
	std::ios_base::sync_with_stdio(false);
	
	unsigned int n;
	std::cin>>n;
	
	VECUINT Minima(n),Maksima(n);
	for(unsigned int i=0;i<n;++i)
		std::cin>>Minima[i]>>Maksima[i];
	
	VECPUII Wyniki(n+1,PUII(0,0));
	Wyniki[n]=PUII(0,1);
	
	for(unsigned int i=n;i>0;){
		unsigned int min=0,max=INF;
		for(unsigned int j=--i;j<n&&j-i<(max=std::min(max,Maksima[j]));++j){
			min=std::max(min,Minima[j]);
			if(j-i+1>=min&&Wyniki[j+1].second){
				if(Wyniki[j+1].first>=Wyniki[i].first)
					Wyniki[i]=PUII(Wyniki[j+1].first+1,Wyniki[j+1].second);
				else if((Wyniki[j+1].first+1)==Wyniki[i].first)
					Wyniki[i].second=(Wyniki[i].second+Wyniki[j+1].second)%INF;
			}
		}
	}
	
	if(Wyniki[0].second)
		std::cout<<(Wyniki[0].first)<<" "<<Wyniki[0].second<<"\n";
	else
		std::cout<<"NIE"<<"\n";
	
	return 0;
}