#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } using mint = atcoder::modint1000000007; ostream& operator<<(ostream& os, const mint& m){ os << m.val(); return os; } template class Compress{ public: vector data; int offset; Compress(vector data_, int offset=0): offset(offset){ data = data_; sort(begin(data), end(data)); data.erase(unique(begin(data), end(data)), end(data)); }; int operator[](T x) { auto p = lower_bound(data.begin(), data.end(), x); assert(x == *p); return offset+(p-data.begin()); } T inv(int x){ return data[x-offset]; } int size(){ return data.size(); } }; template class CumsumGrid{ public: CumsumGrid(vector> v): v(v){ n = v.size(); m = v[0].size(); v_cumsum = vector>(n+1, vector(m+1, T(0))); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++){ v_cumsum[i+1][j+1] = v_cumsum[i+1][j]+v_cumsum[i][j+1]-v_cumsum[i][j]+v[i][j]; } } } /** * sum(v[il:ir)[jl:jr)) */ T sum(int il, int ir, int jl, int jr){ if(ir <= il) return T(0); if(jr <= jl) return T(0); if(ir > n) ir = n; if(jr > m) jr = m; if(il < 0) il = 0; if(jl < 0) jl = 0; return v_cumsum[ir][jr]-v_cumsum[ir][jl]-v_cumsum[il][jr]+v_cumsum[il][jl]; } private: int n, m; vector> v; vector> v_cumsum; }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n; cin >> n; vector a(n), b(n); vector v; for(int i = 0; i < n; i++){ cin >> a[i] >> b[i]; v.push_back(a[i]); v.push_back(b[i]); } auto cp = Compress(v); vector proba(n+1); proba[1] = 1; vector f = {mint(1)}; for(int len = 2; len <= n; len++){ vector fs = {mint(0)}; for(int i = 0; i < f.size(); i++){ fs.push_back(f[i]/(i+1)); } if(len%2 == 0){ // 前より大きい // f(0) = 0になっている f = fs; }else{ // 前より小さい mint f1 = accumulate(fs.begin(), fs.end(), mint(0)); for(int i = 0; i < fs.size(); i++) fs[i] *= -1; fs[0] += f1; f = fs; } for(int i = 0; i < f.size(); i++){ proba[len] += f[i]/(i+1); } } int m = cp.size(); auto dp = vec3d(n, m-1, n+1, mint(0)); for(int j = 0; j < m-1; j++){ int l = cp.data[j], r = cp.data[j+1]; if(r <= a[0] || l >= b[0]) continue; mint p = mint(r-l)/mint(b[0]-a[0]); dp[0][j][1] = p; } for(int i = 1; i < n; i++){ auto v = dp[i-1]; for(int j = 0; j < m-1; j++){ for(int k = 0; k <= n; k++){ v[j][k] *= proba[k]; } } auto cumsum = CumsumGrid(v); for(int j = 0; j < m-1; j++){ int l = cp.data[j], r = cp.data[j+1]; if(r <= a[i] || l >= b[i]) continue; mint p = mint(r-l)/mint(b[i]-a[i]); // 同じ所 for(int k = 1; k <= n; k++){ dp[i][j][k] += dp[i-1][j][k-1]*p; } // 違う場所 if(i%2 == 0){ // 小さくなる dp[i][j][1] += cumsum.sum(j+1, m, 0, n+1)*p; }else{ // 大きくなる dp[i][j][1] += cumsum.sum(0, j, 0, n+1)*p; } } } mint ans = 0; for(int j = 0; j < m-1; j++){ for(int k = 1; k <= n; k++){ ans += dp[n-1][j][k]*proba[k]; } } cout << ans << endl; }