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
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cassert>
using namespace std;
typedef long long LL;
const int MAXN = (1<<20)+1;
const int P = 1000000007;
const int OO = (1<<30)-1;

int low[MAXN];
int high[MAXN];
int last[MAXN];

LL ways[MAXN];
int teams[MAXN];
int n;

int main() {
  assert(1 == scanf("%d", &n));
  for (int i = 0; i < n; ++i) {
    assert(2 == scanf("%d%d", &low[i], &high[i]));
  }

  ways[n] = 1;
  teams[n] = 0;
  int best = 0;
  for (int i = 0; i < n; ++i) {
    last[i] = -1;
  }
  for (int i = n-1; i >= 0; --i) {
    teams[i] = -OO;
    ways[i] = 0;
    int clow = low[i];
    int chigh = high[i];
    for (int j = i + 1; j <= n; ++j) {
      if (j - i > chigh) {
        break;
      }
      if (clow <= j - i and j - i <= chigh) {
        if (ways[j] > 0) {
          if (teams[j] + 1 > teams[i]) {
            teams[i] = teams[j] + 1;
            ways[i] = ways[j];
          } else if (teams[j] + 1 == teams[i]) {
            ways[i] += ways[j];
          }
          if (teams[j] + 1 == teams[i] and teams[j] == best and j == last[best]) {
            break;
          }
        }
      }
      clow = max(clow, low[j]);
      chigh = min(chigh, high[j]);
    }
    ways[i] %= P;
    if (teams[i] > 0 and last[teams[i]] == -1) {
      last[teams[i]] = i;
    }
    best = max(best, teams[i]);
  }
  
  if (teams[0] < 0) {
    printf("NIE\n");
  } else {
    printf("%d %lld\n", teams[0], ways[0]);
  }
  return 0;
}