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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdlib.h>
//---===---
#include <stdio.h>
#include <unistd.h>

typedef unsigned int uint;

char buf_in[4096000];
int buf_in_head = 0;
int buf_in_tail = 0;

static int getChar(void) {
  while (buf_in_head == buf_in_tail) {
    int rv = read(0, buf_in, sizeof(buf_in));
    if (rv > 0) {
      buf_in_head = 0;
      buf_in_tail = rv;
      break;
    };
    if (rv == 0) return EOF;
  }
  return buf_in[buf_in_head++];
}

// only 1 call is safe, and only if previously getChar() had been called.
static void ungetChar(void) {
  --buf_in_head;
}

static uint getUInt() {
  uint v;
  int c;
  for (;;) {
    c = getChar();
    if (c < '0') continue;
    if (c > '9') continue;
    v = c - '0';
    break;
  };
  for (;;) {
    c = getChar();
    if (c < '0') break;
    if (c > '9') break;
    v *= 10;
    v += c - '0';
  };
  ungetChar();
  return v;
}
//---===---

#define MOD (1000000000 + 7)

int n;

#define H1

typedef struct {
  uint c, d, ways, splits;
#ifdef H1
  uint max_splits;
#endif /* H1 */
} tt;

tt T[1000000+1];

#define POSSIBLE(_i_) (T[_i_].ways | T[_i_].splits)

int main (void) {
  int i, j;

  // 1 <= n <= 1,000,000
  n = getUInt();

  for (i = 1; i <= n; ++i) {
    // 1 <= c[i] <= d[i] <= n
    T[i].c = getUInt();
    T[i].d = getUInt();
  };

  T[0].ways = 1;
  T[0].splits = 0;
#ifdef H1
  T[0].max_splits = 0;
#endif /* H1 */
  //printf("*** 0: ways:1 splits:0 max_splits:0\n");

  for (i = 1; i <= n; ++i) {
    uint cnt = 0, min = 0, max = i, w = 0, s = 0;

    for (j = 0; j < i; ++j) {
      uint k = i - j; // i > j, hence k >= 1
      ++cnt;
      if (T[k].c > min) min = T[k].c;
      if (T[k].d < max) max = T[k].d;
      --k; // k >= 0;
#ifdef H1
      if (T[k].max_splits + 1 < s) break; // won't see anything useful
#endif /* H1 */
      if (cnt > max) break; // too much
      if (cnt < min) continue; // not enough
      // valid
      //printf("%d: %d --> %d\n", i, j, k);
      if (!POSSIBLE(k)) continue;
      if (T[k].splits + 1 > s) {
        s = T[k].splits + 1;
        w = T[k].ways;
      } else if (T[k].splits + 1 == s) {
        w += T[k].ways;
        if (w > MOD) w -= MOD;
      };
    };
    T[i].ways = w;
    T[i].splits = s;
#ifdef H1
    T[i].max_splits = T[i - 1].max_splits;
    if (s > T[i].max_splits) T[i].max_splits = s;
#endif /* H1 */
    //printf("*** %d: ways:%u splits:%u max_splits:%u\n", i, w, s, T[i].max_splits);
  };

  if (POSSIBLE(n)) {
    printf("%d %d\n", T[n].splits, T[n].ways);
  } else {
    printf("NIE\n");
  };

  return 0;
}