Boat

input/code.cpp: In member function 'int S::compute_sum()':
input/code.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < coeffs.size(); ++i) {
                     ~~^~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j+1 < coeffs.size(); ++j) {
                       ~~~~^~~~~~~~~~~~~~~

// f^0(x) = 1
// f^n(x) = \sum_{i=0}^(x-1) f^{n-1}(i)
// -->
// f^n(x) = x choose n
// \sum_{i=0}^{a-1} f^n(i) = f^{n+1}(a) = a choose n+1

// Segmentti on funktio muotoa s(x) = c_0 f^0(x) + c_1 f^1(x) + ... + c_m f^m(x)
// siitä prefix sum -->       s'(x) = c_0 f^1(x) + c_1 f^2(x) + ... + c_m f^{m+1}(x)


#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 1e9+7;
int fac[N], ifac[N];
long mmul(long b, long e) {
  if (e == 0) return 1;
  if (e%2) {
    return mmul(b, e-1)*b%M;
  } else {
    long p = mmul(b, e/2);
    return p*p%M;
  }
}
long fbinom(long x, long n) {
  if (n > x) return 0;
  long res = ifac[n];
  for (int i = 0; i < n; ++i) {
    res = res*(x-i)%M;
  }
  return res;
}
struct S {
  int a;
  int sum = 0;
  int csum = 1;
  vector<int> coeffs{};
  vector<int> prec{};
  int compute_sum() {
    sum = 0;
    for (int i = 0; i < coeffs.size(); ++i) {
      sum += long(prec[i])*coeffs[i]%M;
      sum %= M;
    }
    return sum;
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  fac[0] = 1;
  ifac[0] = 1;
  for (long i = 1; i < N; ++i) {
    fac[i] = i*fac[i-1]%M;
    ifac[i] = mmul(fac[i], M-2);
  }
  int n;
  cin >> n;
  int a[n], b[n];
  map<int, S> sg;
  sg[0];
  sg[0].sum = 1;
  sg[0].csum = 0;
  sg[0].coeffs = {1};
  sg[0].prec = {1};
  sg[1];
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
    b[i]++;
    sg[a[i]];
    sg[b[i]];
  }
  int lv = 1e9;
  for (auto it = sg.rbegin(); it != sg.rend(); it++) {
    it->second.a = lv - it->first;
    lv = it->first;
  }
  int csum = 1;
  for (int i = 0; i < n; ++i) {
    auto asg = sg.find(a[i]), bsg = sg.find(b[i]);
    for (auto it = asg; it != bsg; it++) {
      vector<int> &coeffs = it->second.coeffs, &prec = it->second.prec;
      coeffs.insert(coeffs.begin(), 0);
      int ni = prec.size();
      prec.push_back(fbinom(it->second.a, ni+1));
      for (int j = 0; j+1 < coeffs.size(); ++j) {
        coeffs[j] += coeffs[j+1];
        coeffs[j] %= M;
      }
      coeffs[0] += it->second.csum;
      coeffs[0] %= M;
    }
    csum = 0;
    for (auto &p : sg) {
      p.second.csum = csum;
      csum += p.second.compute_sum();
      csum %= M;
    }
  }
  cout << (csum-1+M)%M << endl;
}

Test 1

Group: 1, 2, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 4

Verdict: ACCEPTED

Test 3

Group: 1, 2, 4

Verdict: ACCEPTED

Test 4

Group: 1, 2, 4

Verdict: ACCEPTED

Test 5

Group: 1, 2, 4

Verdict: ACCEPTED

Test 6

Group: 1, 2, 4

Verdict: ACCEPTED

Test 7

Group: 1, 2, 4

Verdict: ACCEPTED

Test 8

Group: 1, 2, 4

Verdict: ACCEPTED

Test 9

Group: 1, 2, 4

Verdict: ACCEPTED

Test 10

Group: 1, 2, 4

Verdict: ACCEPTED

Test 11

Group: 1, 2, 4

Verdict: ACCEPTED

Test 12

Group: 1, 2, 4

Verdict: ACCEPTED

Test 13

Group: 1, 2, 4

Verdict: ACCEPTED

Test 14

Group: 1, 2, 4

Verdict: ACCEPTED

Test 15

Group: 1, 2, 4

Verdict: ACCEPTED

Test 16

Group: 1, 2, 4

Verdict: ACCEPTED

Test 17

Group: 1, 2, 4

Verdict: ACCEPTED

Test 18

Group: 1, 2, 4

Verdict: ACCEPTED

Test 19

Group: 1, 2, 4

Verdict: ACCEPTED

Test 20

Group: 1, 2, 4

Verdict: ACCEPTED

Test 21

Group: 2, 4

Verdict: ACCEPTED

Test 22

Group: 2, 4

Verdict: ACCEPTED

Test 23

Group: 2, 4

Verdict: ACCEPTED

Test 24

Group: 2, 4

Verdict: ACCEPTED

Test 25

Group: 2, 4

Verdict: ACCEPTED

Test 26

Group: 2, 4

Verdict: ACCEPTED

Test 27

Group: 2, 4

Verdict: ACCEPTED

Test 28

Group: 2, 4

Verdict: ACCEPTED

Test 29

Group: 2, 4

Verdict: ACCEPTED

Test 30

Group: 2, 4

Verdict: ACCEPTED

Test 31

Group: 2, 4

Verdict: ACCEPTED

Test 32

Group: 2, 4

Verdict: ACCEPTED

Test 33

Group: 2, 4

Verdict: ACCEPTED

Test 34

Group: 2, 4

Verdict: ACCEPTED

Test 35

Group: 2, 4

Verdict: ACCEPTED

Test 36

Group: 2, 4

Verdict: ACCEPTED

Test 37

Group: 2, 4

Verdict: ACCEPTED

Test 38

Group: 2, 4

Verdict: ACCEPTED

Test 39

Group: 2, 4

Verdict: ACCEPTED

Test 40

Group: 2, 4

Verdict: ACCEPTED

Test 41

Group: 3, 4

Verdict: ACCEPTED

Test 42

Group: 3, 4

Verdict: ACCEPTED

Test 43

Group: 3, 4

Verdict: ACCEPTED

Test 44

Group: 3, 4

Verdict: ACCEPTED

Test 45

Group: 3, 4

Verdict: ACCEPTED

Test 46

Group: 3, 4

Verdict: ACCEPTED

Test 47

Group: 3, 4

Verdict: ACCEPTED

Test 48

Group: 3, 4

Verdict: ACCEPTED

Test 49

Group: 3, 4

Verdict: ACCEPTED

Test 50

Group: 3, 4

Verdict: ACCEPTED

Test 51

Group: 3, 4

Verdict: ACCEPTED

Test 52

Group: 3, 4

Verdict: ACCEPTED

Test 53

Group: 3, 4

Verdict: ACCEPTED

Test 54

Group: 3, 4

Verdict: ACCEPTED

Test 55

Group: 3, 4

Verdict: ACCEPTED

Test 56

Group: 3, 4

Verdict: ACCEPTED

Test 57

Group: 3, 4

Verdict: ACCEPTED

Test 58

Group: 3, 4

Verdict: ACCEPTED

Test 59

Group: 3, 4

Verdict: ACCEPTED

Test 60

Group: 3, 4

Verdict: ACCEPTED

Test 61

Group: 4

Verdict: ACCEPTED

Test 62

Group: 4

Verdict: ACCEPTED

Test 63

Group: 4

Verdict: ACCEPTED

Test 64

Group: 4

Verdict: ACCEPTED

Test 65

Group: 4

Verdict: ACCEPTED

Test 66

Group: 4

Verdict: ACCEPTED

Test 67

Group: 4

Verdict: ACCEPTED

Test 68

Group: 4

Verdict: ACCEPTED

Test 69

Group: 4

Verdict: ACCEPTED

Test 70

Group: 4

Verdict: ACCEPTED

Test 71

Group: 4

Verdict: ACCEPTED

Test 72

Group: 4

Verdict: ACCEPTED

Test 73

Group: 4

Verdict: ACCEPTED

Test 74

Group: 4

Verdict: ACCEPTED

Test 75

Group: 4

Verdict: ACCEPTED

Test 76

Group: 4

Verdict: ACCEPTED

Test 77

Group: 4

Verdict: ACCEPTED

Test 78

Group: 4

Verdict: ACCEPTED

Test 79

Group: 4

Verdict: ACCEPTED

Test 80

Group: 4

Verdict: ACCEPTED