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
48
49
50
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

pair <long long,long long> dn[1000007];
int n;
pair <int,int> wym[1000007];
int maxi;
int mini;

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		scanf("%d%d", &wym[i].first, &wym[i].second);
	}
	dn[0].second=1;
	for (int i=1; i<=n; i++)
	{
		maxi=wym[i].second;
		mini=wym[i].first;
		for (int j=0; j<maxi && j<i; j++)
		{
			maxi=min(maxi, wym[i-j].second);
			mini=max(mini, wym[i-j].first);
			if (j>=maxi)
			break;
			if (j+1>=mini)
			{
				if (dn[i-j-1].first+1>dn[i].first)
				{
					dn[i].first=dn[i-j-1].first+1;
					dn[i].second=dn[i-j-1].second;
				}
				else if (dn[i-j-1].first+1==dn[i].first)
				{
					dn[i].second+=dn[i-j-1].second;
				}
			}
		}
		dn[i].second=dn[i].second%1000000007;
	}
	if (dn[n].first)
	printf("%lld %lld", dn[n].first, dn[n].second);
	else
	printf("NIE");
	return 0;
}