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
51
52
53
54
55
56
#include<cstdio>
#define MAXD 1000005
#define MOD 1000000007

int n;
int C[MAXD], D[MAXD];
int R[MAXD], T[MAXD], B[MAXD];

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&C[i],&D[i]);

    R[n] = 0; T[n] = 1; B[n] = -1;
   
    int bestT = -1;
    
    for(int i=n-1;i>=0;i--){
        int best = -1, bestV = 0;
        int a = C[i], b = D[i];
        int last = -1;
        for(int j=0;i+j<n;j++){         
            a = max(a, C[i+j]);
            b = min(b, D[i+j]);
            
            if(b<j+1 || B[i+j]+1<best)break;
            if(a <= j+1){
                if(R[i+j+1]+1 > best){
                    best = R[i+j+1]+1;
                    bestV = T[i+j+1];
                }else
                if(R[i+j+1]+1 == best)
                    bestV = (bestV+T[i+j+1])%MOD;
            }                
        }
        
        if(best>0){
            R[i] = best;
            T[i] = bestV;
        }else{
            R[i] = -1;
            T[i] = 0;
        }
        B[i] = max(R[i], B[i+1]);
        
        //if((i&0xfff)==0)printf("%d\n",n-i);
    }
    
    if(R[0]==-1)
        printf("NIE\n");
    else{
        printf("%d %d\n",R[0], T[0]);
    }
}