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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <complex>
#include <sstream>
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int,int> PII;
 
#define REP(i,n) for(int i=0;i<(n);++i)
#define SIZE(c) ((int)((c).size()))
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)
#define ALL(v) (v).begin(), (v).end()
 
#define pb push_back
#define mp make_pair
#define st first
#define nd second

int A[1000001],B[1000001];
int M[1000001];

const int MOD = 1000000007;

PII add(PII a, PII b) {
  if (a.st != b.st) return a.st > b.st ? a : b;
  return PII(a.st, (a.nd + b.nd)%MOD);
}

PII T[2222222];
int U;
void init(int N) {
  U = 1;
  while (U < N + 2) U <<= 1;
  REP(i,2*U) T[i] = PII(-1, 0);
}

void update(int v, PII value) {
  v += U;
  T[v] = value;
  while (v >>= 1) {
    T[v] = add(T[2*v], T[2*v+1]);
  }
}

PII get(int A, int B, int v = 1, int L = 0, int R = U-1) {
  if (A <= L && R <= B) return T[v];
  if (R < A || B < L) return PII(-1,0);
  return add(get(A,B,2*v,L,(L+R)/2), get(A,B,2*v+1,(L+R)/2+1,R));
}

void scase() {
  int N;
  scanf("%d",&N);
  REP(i,N) scanf("%d%d",&A[i],&B[i]);
  REP(i,N) M[i] = min(N, i + B[i]);
  REP(i,N) if (i >= B[i]) M[i - B[i]] = min(M[i - B[i]], i);
  FORD(i,N-1,0) M[i] = min(M[i], M[i+1]);

  init(N);
  update(N, PII(0,1));
  deque<int> S;
  FORD(i,N,0) {
    while (!S.empty() && A[S.front()] <= A[i]) S.pop_front();
    S.push_front(i);
    PII res(-1,0);
    
    int start;
    if (S.size() < 5) start = 0;
    else {
      int L = 0, R = S.size() - 2;
      while (L < R) {
        int s = (L + R) / 2;
        bool good = (i + A[S[s]] <= S[s+1]);      
        if (good) R = s;
        else L = s + 1;
      }
      start = L;
    }
    
    FOR(s, start, S.size()) {
      int first = max(S[s] + 1, A[S[s]] + i);
      if (first > M[i]) break;
      int last = s == S.size() - 1 ? N : S[s+1];
      last = min(last, M[i]);
      PII tmp = get(first, last);
      res = add(res, get(first, last));
    }
    if (res.st > -1) res.st++;
    update(i, res);
  }

  PII res = get(0,0);
  if (res.st > -1) {
    printf("%d %d\n", res.st, res.nd);
  } else printf("NIE\n");
}

int main() {
  scase();
}