[BZOJ4584][Apio2016]赛艇

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
	return x * f;
}

#define maxn 510
#define MOD 1000000007
#define LL long long

int n, num[maxn<<1], cntn;
struct Line {
	int l, r;
	Line() {}
	Line(int _, int __): l(_), r(__) {}
	int len() { return r - l + 1; }
} sch[maxn], ls[maxn<<1];

int invnum[maxn], C[maxn<<1][maxn], invC[maxn<<1][maxn];
void gcd(LL a, LL b, LL& x, LL& y) {
	if(!b){ x = 1; y = 0; return ; }
	gcd(b, a % b, y, x); y -= a / b * x;
	return ;
}
int Inv(LL a) {
	LL x, y;
	gcd(a, MOD, x, y);
	return (x % MOD + MOD) % MOD;
}
void init() {
	for(int i = 1; i <= n; i++) invnum[i] = Inv(i);
	for(int i = 1; i < cntn; i++) {
		C[i][0] = invC[i][0] = 1;
		for(int j = 1; j <= min(ls[i].len(), n); j++)
			C[i][j] = (LL)C[i][j-1] * (ls[i].len() - j + 1) % MOD * invnum[j] % MOD,
			invC[i][j] = Inv(C[i][j]);
	}
	return ;
}

int f[maxn<<1][maxn], sum[maxn<<1];

int main() {
	n = read();
	for(int i = 1; i <= n; i++) {
		int l = read(), r = read() + 1;
		sch[i] = Line(l, r);
		num[++cntn] = l; num[++cntn] = r;
	}
	sort(num + 1, num + cntn + 1);
	cntn = unique(num + 1, num + cntn + 1) - num - 1;
	for(int i = 1; i < cntn; i++) ls[i] = Line(num[i], num[i+1] - 1);
	for(int i = 1; i <= n; i++)
		sch[i].l = lower_bound(num + 1, num + cntn + 1, sch[i].l) - num,
		sch[i].r = lower_bound(num + 1, num + cntn + 1, sch[i].r) - num;
	
	init();
	for(int j = 0; j < cntn; j++) sum[j] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = sch[i].r - 1; j >= sch[i].l; j--) {
			for(int k = min(i, ls[j].len()); k >= 2; k--) {
				f[j][k] += (LL)f[j][k-1] * invC[j][k-1] % MOD * C[j][k] % MOD;
				if(f[j][k] >= MOD) f[j][k] -= MOD;
			}
			f[j][1] += (LL)sum[j-1] * ls[j].len() % MOD;
			if(f[j][1] >= MOD) f[j][1] -= MOD;
		}
		sum[0] = 1;
		for(int j = 1; j < cntn; j++) {
			sum[j] = sum[j-1];
			int mxk = min(i, ls[j].len());
			for(int k = 1; k <= mxk; k++) {
				sum[j] += f[j][k];
				if(sum[j] >= MOD) sum[j] -= MOD;
			}
		}
	}
	
	printf("%d\n", ((sum[cntn-1] - sum[0]) % MOD + MOD) % MOD);
	
	return 0;
}