// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // #undef DEBUG // #define DEBUG // DEBUG {{{ #include #include #include #include #include #include #include #include #include template < int n, class... T > typename std::enable_if< (n >= sizeof...(T)) >::type __output_tuple( std::ostream &, std::tuple< T... > const &) {} template < int n, class... T > typename std::enable_if< (n < sizeof...(T)) >::type __output_tuple( std::ostream &os, std::tuple< T... > const &t) { os << (n == 0 ? "" : ", ") << std::get< n >(t); __output_tuple< n + 1 >(os, t); } template < class... T > std::ostream &operator<<(std::ostream &os, std::tuple< T... > const &t) { os << "("; __output_tuple< 0 >(os, t); os << ")"; return os; } template < class T, class U > std::ostream &operator<<(std::ostream &os, std::pair< T, U > const &p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template < class T > std::ostream &operator<<(std::ostream &os, const std::stack< T > &a) { os << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) os << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); os << "}"; return os; } template < class T, class Container, class Compare > std::ostream &operator<<(std::ostream &os, std::priority_queue< T, Container, Compare > a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } template < class T, class Container > std::ostream &operator<<(std::ostream &os, std::queue< T, Container > a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } #ifdef DEBUG #if !defined(DEBUG_OUT) #define DEBUG_OUT std::cerr #endif #define dump(...) \ [&]() { \ auto __debug_tap = std::make_tuple(__VA_ARGS__); \ DEBUG_OUT << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \ << std::endl; \ }() template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << std::endl; } } template < class T > inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << std::endl; } template < class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type, class = typename std::enable_if< !std::is_same< T, std::string >::value >::type > std::ostream &operator<<(std::ostream &os, const T &a) { os << "{"; for(auto ite = begin(a); ite != end(a); ++ite) os << (ite == begin(a) ? "" : ", ") << *ite; os << "}"; return os; } #else #define dump(...) ((void) 42) #define dump2D(...) ((void) 42) #define dump1D(...) ((void) 42) template < class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type, class = typename std::enable_if< !std::is_same< T, std::string >::value >::type > std::ostream &operator<<(std::ostream &os, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) os << (ite == begin(a) ? "" : " ") << *ite; return os; } #endif // }}} /// --- Modulo Integer {{{ /// #include template < long long mod = static_cast< long long >(1e9 + 7) > struct ModuloInteger { static_assert(mod > 0, "mod must be positive"); static_assert(mod <= 3037000499, "mod is too big"); using integer = long long; static ModuloInteger unused; // math {{{ static inline integer extgcd(integer a, integer b, integer &x, integer &y) { integer d; return b == 0 ? (x = a < 0 ? -1 : 1, y = 0, a < 0 ? -a : a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); } static inline integer modinv(integer a) { integer x = 0, y = 0; extgcd(a, mod, x, y); if(x < 0) x += mod; else if(x == mod) x = 0; return x; } static inline integer modpow(integer a, long long b) { if(b < 0) b = -b, a = modinv(a); integer r = 1; a %= mod; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } // }}} integer val; constexpr ModuloInteger() : val(0) {} constexpr ModuloInteger(integer t) { val = t % mod; if(val < 0) val += mod; } private: // strict constructor constexpr ModuloInteger(integer t, int) : val(t) {} public: template < class T > explicit operator T() { return T(val); } // operator bool() { return bool(val); } // ModuloInteger [=] ModuloInteger {{{ ModuloInteger operator+(ModuloInteger const &rhs) const { ModuloInteger tmp = *this; tmp += rhs; return tmp; } ModuloInteger operator-(ModuloInteger const &rhs) const { ModuloInteger tmp = *this; tmp -= rhs; return tmp; } ModuloInteger operator*(ModuloInteger const &rhs) const { ModuloInteger tmp = *this; tmp *= rhs; return tmp; } ModuloInteger operator/(ModuloInteger const &rhs) const { ModuloInteger tmp = *this; tmp /= rhs; return tmp; } ModuloInteger &operator+=(ModuloInteger const &rhs) { val = val + rhs.val; if(val >= mod) val -= mod; return *this; } ModuloInteger &operator-=(ModuloInteger const &rhs) { return *this += -rhs; } ModuloInteger &operator*=(ModuloInteger const &rhs) { val = val * rhs.val % mod; return *this; } ModuloInteger &operator/=(ModuloInteger const &rhs) { return *this *= rhs.inv(); } // }}} // increment, decrement {{{ ModuloInteger operator++(int) { ModuloInteger tmp = *this; val = val + 1; if(val >= mod) val = 0; return tmp; } ModuloInteger operator--(int) { ModuloInteger tmp = *this; val = val == 0 ? mod - 1 : val - 1; return tmp; } ModuloInteger &operator++() { val = val + 1; if(val >= mod) val = 0; return *this; } ModuloInteger &operator--() { val = val == 0 ? mod - 1 : val - 1; return *this; } // }}} ModuloInteger operator-() const { return ModuloInteger(val == 0 ? 0 : mod - val, 0); } // ModuloInteger [=] T {{{ template < typename T > ModuloInteger operator+(T const &rhs) const { return ModuloInteger(val + rhs % mod); } template < typename T > ModuloInteger operator-(T const &rhs) const { return ModuloInteger(mod + val - rhs % mod); } template < typename T > ModuloInteger operator*(T const &rhs) const { return ModuloInteger(val * (rhs % mod)); } template < typename T > ModuloInteger operator/(T const &rhs) const { return ModuloInteger(val * modinv(rhs)); } template < typename T > ModuloInteger &operator+=(T const &rhs) { val = (mod + val + rhs % mod) % mod; return *this; } template < typename T > ModuloInteger &operator-=(T const &rhs) { val = (mod + val - rhs % mod) % mod; return *this; } template < typename T > ModuloInteger &operator*=(T const &rhs) { val = val * (mod + rhs % mod) % mod; return *this; } template < typename T > ModuloInteger &operator/=(T const &rhs) { val = val * modinv(rhs) % mod; return *this; } // }}} ModuloInteger inv() const { return ModuloInteger(modinv(val), 0); } ModuloInteger operator~() const { return inv(); } friend std::ostream &operator<<(std::ostream &os, ModuloInteger const &mv) { os << mv.val; return os; } // equality operator {{{ ModuloInteger operator==(const ModuloInteger &a) const { return val == a.val; } ModuloInteger operator!=(const ModuloInteger &a) const { return val != a.val; } ModuloInteger operator==(const integer &a) const { return val == ModuloInteger(a); } ModuloInteger operator!=(const integer &a) const { return val != ModuloInteger(a); } // }}} // T ModuloInteger {{{ friend constexpr ModuloInteger operator+(integer a, ModuloInteger const &mv) { return ModuloInteger(a % mod + mv.val); } friend constexpr ModuloInteger operator-(integer a, ModuloInteger const &mv) { return ModuloInteger(a % mod - mv.val); } friend constexpr ModuloInteger operator*(integer a, ModuloInteger const &mv) { return ModuloInteger((mod + a % mod) * mv.val % mod, 0); } friend constexpr ModuloInteger operator/(integer a, ModuloInteger const &mv) { return ModuloInteger((mod + a % mod) * modinv(mv.val) % mod, 0); } // }}} // power {{{ ModuloInteger operator^(integer x) const { return pow(*this, x); } ModuloInteger &operator^=(integer x) { val = modpow(val, x); return *this; } friend ModuloInteger pow(ModuloInteger x, integer y) { return ModuloInteger(modpow(x.val, y), 0); } // }}} }; template < long long mod > ModuloInteger< mod > ModuloInteger< mod >::unused(mod, 0); /// }}}--- /// using modint = ModuloInteger<>; struct Poly { vector poly; Poly() { poly.push_back(0); } Poly(modint a_0) { poly.push_back(a_0); } Poly seki () { Poly f; f.poly.resize(poly.size() + 1); for(size_t i = 0; i < poly.size(); i++) f.poly[i+1] = poly[i] / (i+1); return f; } modint get(modint x) const { modint t = 1; modint r = 0; for(size_t i = 0; i < poly.size(); i++, t = t * x) r += poly[i] * t; return r; } Poly mul(modint x) const { Poly f; f.poly.resize(poly.size()); for(size_t i = 0; i < poly.size(); i++) f.poly[i] = poly[i] * x; return f; } Poly mx() const { Poly f; f.poly.resize(poly.size()); for(size_t i = 0; i < poly.size(); i++) f.poly[i] = poly[i] * (i % 2 == 0 ? 1 : -1); return f; } bool operator<(const Poly&) const { return 0; } friend ostream& operator<<(ostream& os, const Poly& p) { os << "Poly: "; for(size_t i = 0; i < p.poly.size(); i++) os << p.poly[i] << " x^" << i << (i + 1 == p.poly.size() ? "" : " + "); return os; } }; using R = pair; using P = pair; constexpr ll inf = 1e18; void sekibun(set

& st) { modint sum = 0; set

nst; for(auto e : st) { Poly p; R r; tie(r, p) = e; p = p.seki(); p.poly[0] += sum - p.get(r.first); sum = p.get(r.second); nst.insert(P(r, p)); } st = nst; } modint sget(set

& st, ll u) { assert(st.size()); if(u < st.begin()->first.first) { return 0; } for(auto e : st) { Poly p; R r; tie(r, p) = e; if(r.first < u && u < r.second) { return p.get(u); } } { Poly p; R r; tie(r, p) = *prev(st.end()); return p.get(r.second); } } void sp(set

& st, ll u) { assert(st.size()); if(u < st.begin()->first.first) { st.insert(P(R(u, st.begin()->first.first), Poly(0))); return; } for(auto e : st) { Poly p; R r; tie(r, p) = e; if(r.first < u && u < r.second) { st.erase(e); st.insert(P(R(r.first, u), p)); st.insert(P(R(u, r.second), p)); return; } if(r.first == u || u == r.second) return; } st.insert(P(R(prev(st.end())->first.second, u), Poly(sget(st, inf)))); } void only(set

& st, ll a, ll b) { set

nst; for(auto e : st) { Poly p; R r; tie(r, ignore) = e; if(a <= r.first && r.second <= b) { e.second = e.second.mul(modint(1) / (b - a)); nst.insert(e); } } st = nst; } void mxall(set

& st) { set

nst; for(auto e : st) { Poly p; R r; tie(r, ignore) = e; e.second = e.second.mx(); swap(e.first.first, e.first.second); e.first.first *= -1, e.first.second *= -1; nst.insert(e); } st = nst; } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); int n; cin >> n; set

st; // st.insert(P(R(-inf,inf), Poly(1))); for(int i = 0; i < n; i++) { ll a, b; cin >> a >> b; if(i == 0) { st.insert(P(R(a, b), Poly(1).mul(modint(1) / (b - a)))); } else { if(i % 2 == 0) { mxall(st); sekibun(st); sp(st, -a); sp(st, -b); only(st, -b, -a); mxall(st); } else { sekibun(st); sp(st, a); sp(st, b); only(st, a, b); } } dump(st); dump(i, sget(st, inf)); } sekibun(st); cout << sget(st, inf) << endl; return 0; }