记录编号	260003	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO2016]划艇	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	21.323 s
提交时间	2016-05-12 14:50:15	内存使用	8.14 MiB

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 1010
using namespace std;
typedef long long ll;
const int md = 1000000007;
int n, a[maxn], b[maxn], h[maxn];
ll inv[maxn];

ll power_mod(ll a, ll b = md - 2){
	ll ret = 1;
	while(b > 0){
		if(b & 1)ret = ret * a % md;
		b >>= 1;
		a = a * a % md;
	}return ret;
}

struct Segment{
	int l, r, cnt, n;
	ll v[maxn], sum;
	bool operator<(const Segment& k)const{
		if(l != k.l)return l < k.l;
		return r < k.r;
	}
	
	void modify(ll val){
		if(l == r){sum += val; if(sum >= md)sum -= md;return;}
		v[cnt ++] = val % md;
	 	int c = cnt; sum = 0;
		for(int i = 0; i < cnt; i ++){
			(v[i] *= (n + c - 1) * inv[c] % md) %= md;
			sum += v[i], c --;
			if(sum >= md)sum -= md;
		}
	}
}p[maxn];

int amt;

void update(int L, int R){
	int l = lower_bound(p+1, p+1+amt, (Segment){L, 0}) - p;
	int r = lower_bound(p+1, p+1+amt, (Segment){R + 1, 0}) - p;
	r --;  ll v = 0;
	for(int i = 1; i < l; i ++)
	    (v += p[i].sum) %= md;
	for(int i = l; i <= r; i ++){
        ll tmp = p[i].sum;
		p[i].modify(v + 1);
		v += tmp; if(v >= md) v -= md;
	}
}

int main(){
	freopen("boat.in", "r", stdin);
	freopen("boat.out", "w", stdout);
	scanf("%d", &n);
	
	inv[0] = inv[1] = 1;
	for(int i = 2; i <= n; i ++)
	    inv[i] = power_mod(i);
	    
	int cnt = 0;
	    
	for(int i = 1; i <= n; i ++){
	    scanf("%d%d", &a[i], &b[i]);
		h[++ cnt] = a[i], h[++ cnt] = b[i] + 1;
	}
	
	sort(h + 1, h + 1 + cnt);
	cnt = unique(h + 1, h + 1 + cnt) - h - 1;
	
	for(int i = 1; i < cnt; i ++)
		p[++ amt] = (Segment){h[i], h[i+1] - 1};
	p[++ amt] = (Segment){h[cnt], h[cnt]};

	for(int i = 1; i <= amt; i ++)
		p[i].n = p[i].r - p[i].l + 1;
	
	for(int i = 1; i <= n; i ++)
	    update(a[i], b[i]);
	ll ans = 0;
	for(int i = 1; i <= amt; i ++){
		ans += p[i].sum;
		if(ans >= md)ans -= md;
	}
	printf("%lld\n", (ans + md) % md);
	return 0;
}