結果
| 問題 | No.907 Continuous Kadomatu |
| ユーザー |
 btk
|
| 提出日時 | 2019-10-11 23:58:23 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 901 ms / 2,000 ms |
| コード長 | 24,277 bytes |
| コンパイル時間 | 2,430 ms |
| コンパイル使用メモリ | 220,952 KB |
| 実行使用メモリ | 28,592 KB |
| 最終ジャッジ日時 | 2024-11-25 18:15:20 |
| 合計ジャッジ時間 | 5,747 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 16 ms
27,868 KB |
| testcase_01 | AC | 15 ms
27,868 KB |
| testcase_02 | AC | 16 ms
27,864 KB |
| testcase_03 | AC | 15 ms
27,740 KB |
| testcase_04 | AC | 15 ms
27,776 KB |
| testcase_05 | AC | 23 ms
27,868 KB |
| testcase_06 | AC | 14 ms
27,872 KB |
| testcase_07 | AC | 17 ms
27,868 KB |
| testcase_08 | AC | 21 ms
27,868 KB |
| testcase_09 | AC | 18 ms
27,868 KB |
| testcase_10 | AC | 25 ms
27,872 KB |
| testcase_11 | AC | 36 ms
27,776 KB |
| testcase_12 | AC | 37 ms
27,776 KB |
| testcase_13 | AC | 41 ms
27,776 KB |
| testcase_14 | AC | 45 ms
27,904 KB |
| testcase_15 | AC | 43 ms
28,032 KB |
| testcase_16 | AC | 47 ms
27,904 KB |
| testcase_17 | AC | 46 ms
27,776 KB |
| testcase_18 | AC | 45 ms
27,832 KB |
| testcase_19 | AC | 44 ms
27,828 KB |
| testcase_20 | AC | 19 ms
28,032 KB |
| testcase_21 | AC | 12 ms
27,828 KB |
| testcase_22 | AC | 12 ms
27,824 KB |
| testcase_23 | AC | 874 ms
28,592 KB |
| testcase_24 | AC | 901 ms
28,576 KB |
| testcase_25 | AC | 13 ms
27,776 KB |
| testcase_26 | AC | 12 ms
27,832 KB |
| testcase_27 | AC | 12 ms
27,904 KB |
| testcase_28 | AC | 12 ms
27,956 KB |
| testcase_29 | AC | 12 ms
27,776 KB |
コンパイルメッセージ
main.cpp:503:13: warning: #pragma once in main file
503 | # pragma once
| ^~~~
ソースコード
// https://yukicoder.me/problems/no/907
#define CIN_ONLY
#define DECIMAL_DIGITS 10
#define STATIC_MOD 1e9 + 7
#ifdef BTK
/*<head>*/
# include "Template.hpp"
# include "num/ModInt.hpp"
/*</head>*/
#else
/*<body>*/
/* #region auto includes */
/* #region stl */
/*<stl>*/
# include <bits/stdc++.h>
# include <sys/types.h>
# include <unistd.h>
using namespace std;
/*</stl>*/
/* #endregion */
/* #region template/IncludeSTL.hpp*/
/**
* @file IncludeSTL.hpp
* @author btk
* @brief 標準ライブラリをincludeするだけ
* @version 0.1
* @date 2019-07-21
* @todo 何故か2回includeされる（展開scriptに
* @copyright Copyright (c) 2019
*
*/
/* #endregion */
/* #region template/Macro.hpp*/
/**
* @file Macro.hpp
* @author btk
* @brief マクロとか，LLとか
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*
*/
//! LL
using LL = long long;
/**
* @def DEBUG
* @brief デバッグ用のif文 提出時はif(0)で実行されない
*/
/*</head>*/
# ifdef BTK
# define DEBUG if (1)
# else
# ifdef CIN_ONLY
# define FAST_IO
# endif
# define DEBUG if (0)
# endif
/**
* @def ALL(v)
* @brief
* ALLマクロ
*/
# define ALL(v) (v).begin(), (v).end()
/**
* @def REC(ret, ...)
* @brief
* 再帰ラムダをするためのマクロ
*/
# define REC(ret, ...) std::function<ret(__VA_ARGS__)>
/**
* @def VAR_NAME(var)
* @brief 変数名を取得する
*/
# define VAR_NAME(var) # var
/**
* @brief
* rangeで生まれる使わない変数を消す用（警告消し）
*/
template <typename T>
inline T& unused_var(T& v) {
return v;
}
/* #endregion */
/* #region template/IO.hpp*/
/**
* @file IO.hpp
* @author btk
* @brief cin高速化とか，出力の小数桁固定とか
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*/
/**
* @brief 入出力の設定を行うための構造体
*/
struct cww {
/**
* @brief Construct a new cww::cww object
* @details
* CIN_ONLYを定義すると，submit時にcinとscanfの同期を切る設定が走る
* DECIMAL_DIGITSを定義すると，doubleの出力時指定した桁数分小数部を吐くようになる
*/
cww() {
# ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(0);
# endif
# ifdef DECIMAL_DIGITS
cout << fixed;
cout << setprecision(DECIMAL_DIGITS);
# endif
}
};
//! 入出力設定構造体を実体化
cww star;
/**
* @brief
* vectorに直接cin流すためのやつ
* @tparam T
* @param is
* @param v
* @return istream&
*/
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& it : v) is >> it;
return is;
}
/* #endregion */
/* #region template/Loop.hpp*/
/**
* @file Loop.hpp
* @author btk
* @brief rangeとかループ系のクラス
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*
*/
/**
* @brief
* rangeを逆向きに操作したいとき用
* @details
* ループの範囲は[bg,ed)なので注意
* @see range
*/
class reverse_range {
private:
struct I {
int x;
int operator*() { return x - 1; }
bool operator!=(I& lhs) { return x > lhs.x; }
void operator++() { --x; }
};
I i, n;
public:
/**
* @brief Construct a new reverse range object
*
* @param n
*/
reverse_range(int n) : i({0}), n({n}) {}
/**
* @brief Construct a new reverse range object
*
* @param i
* @param n
*/
reverse_range(int i, int n) : i({i}), n({n}) {}
/**
* @brief
* begin iterator
* @return I&
*/
I& begin() { return n; }
/**
* @brief
* end iterator
* @return I&
*/
I& end() { return i; }
};
/**
* @brief
* python みたいな range-based for を実現
* @details
* ループの範囲は[bg,ed)なので注意
* !つけると逆向きにループが回る (reverse_range)
* 空間計算量はO(1)
* 使わない変数ができて警告が出がちなので，unused_varとかを使って警告消しするとよい
*/
class range {
private:
struct I {
int x;
int operator*() { return x; }
bool operator!=(I& lhs) { return x < lhs.x; }
void operator++() { ++x; }
};
I i, n;
public:
/**
* @brief Construct a new range object
*
* @param n
*/
range(int n) : i({0}), n({n}) {}
/**
* @brief Construct a new range object
*
* @param i
* @param n
*/
range(int i, int n) : i({i}), n({n}) {}
/**
* @brief
* begin iterator
* @return I&
*/
I& begin() { return i; }
/**
* @brief
* end iterator
* @return I&
*/
I& end() { return n; }
/**
* @brief
* 逆向きに参照するrange(reverse_rangeを取得できるs)
* @return reverse_range
*/
reverse_range operator!() { return reverse_range(*i, *n); }
};
/* #endregion */
/* #region template/MinMaxOperation.hpp*/
/**
* @file MinMaxOperation.hpp
* @author btk
* @brief 最大値とか最小値を求める
* @version 0.1
* @date 2019-07-04
*
* @copyright Copyright (c) 2019
*
*/
/**
* @brief 2項の最小値求める
*
* @tparam T
*/
template <typename T>
struct min_op {
/**
* @brief 本体
*
* @param l
* @param r
* @return T
*/
static T exec(const T l, const T r) { return l < r ? l : r; }
};
/**
* @brief 2項の最大値求める
*
* @tparam T
*/
template <typename T>
struct max_op {
/**
* @brief 本体
*
* @param l
* @param r
* @return T
*/
static T exec(const T l, const T r) { return l > r ? l : r; }
};
/**
* @brief テンプレート再帰の末尾
*
* @tparam F 二項演算
* @tparam T
* @param v
* @return T
*/
template <typename F, typename T>
inline T multi_op(T&& v) {
return v;
}
/**
* @brief 複数項における演算の結果を返す
*
* @tparam F
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template <typename F, typename T, typename... Ts>
inline T multi_op(const T head, Ts&&... tail) {
return F::exec(head, multi_op<F>(tail...));
}
/**
* @brief 複数項の最小値
* @see multi_op
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template <typename T, typename... Ts>
inline T multi_min(T&& head, Ts&&... tail) {
return multi_op<min_op<T>>(head, tail...);
}
/**
* @brief 複数項の最大値
* @see multi_op
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template <typename T, typename... Ts>
inline T multi_max(T&& head, Ts&&... tail) {
return multi_op<max_op<T>>(head, tail...);
}
/**
* @brief
* 先頭の値をFで参照する関数に基づいて変更できたらする
* @tparam F
* @tparam T
* @tparam Ts
* @param target
* @param candidates
* @return true
* @return false
*/
template <typename F, typename T, typename... Ts>
inline bool ch_op(T& target, Ts&&... candidates) {
const T old = target;
target = multi_op<F>(target, candidates...);
return old != target;
}
/**
* @brief change min
* @tparam T 型
* @param target 変更する値
* @param candidates
* @return 更新があればtrue
*/
template <typename T, typename... Ts>
inline bool chmin(T& target, Ts&&... candidates) {
return ch_op<min_op<T>>(target, candidates...);
}
/**
* @brief chminのmax版
* @see chmin
* @tparam T 型
* @param target 変更する値
* @param candidates
* @return 更新があればtrue
*/
template <typename T, typename... Ts>
inline bool chmax(T& target, Ts&&... candidates) {
return ch_op<max_op<T>>(target, candidates...);
}
/* #endregion */
/* #region template/Random.hpp*/
/**
* @file Random.hpp
* @author btk
* @brief 乱数生成系
* @version 0.1
* @date 2019-07-13
* @copyright Copyright (c) 2019
*/
//! 乱数のシード値をプロセスIDとして取得
const pid_t pid = getpid();
/**
* @brief XorShift32の実装
*/
class XorShift32 {
private:
//! XorShiftの現在の値
unsigned value;
/**
* @brief XorShift32のアルゴリズムに基づいて value を更新
*/
inline void update() {
value = value ^ (value << 13);
value = value ^ (value >> 17);
value = value ^ (value << 5);
}
/**
* @brief 値を更新し，更新前の値を返却
* @return unsigned 呼び出し時の value を用いる
*/
inline unsigned get() {
unsigned v = value;
update();
return v;
}
public:
/**
* @brief [0, 2^bit) の範囲の乱数値を取り出す
* @tparam デフォルトは31
* @return int
*/
template <int bit = 31>
inline int next_int() {
return (int)(get() >> (32 - bit));
}
/**
* @brief [-2^bit,2^bit)の範囲の乱数値を取り出す
* @tparam デフォルトは31
* @return int
*/
template <int bit = 31>
inline int next_signed() {
unsigned v = get();
return (int)((v >> (31 - bit)) - (1 << (bit)));
}
/**
* @brief next_int呼び出し時の最大値を取得
* @tparam 31
* @return int
*/
template <int bit = 31>
inline int range_max() {
return (int)((1u << bit) - 1);
};
/**
* @brief Construct a new XorShift32 object
* @param seed
* @details 初期シードをvalueとするXorShift32のインスタンスを生成
*/
XorShift32(const unsigned seed) {
value = seed;
update();
}
/**
* @brief Construct a new XorShift 32 object
* @details 初期シードをプロセスIDとするXorShift32のインスタンスを生成
*/
XorShift32() : XorShift32(pid) {}
};
/* #endregion */
/* #region Template.hpp*/
/**
* @file Template.hpp
* @brief 競技プログラミング用テンプレート
* @author btk15049
* @date 2019/05/02
*/
/* #endregion */
/* #region num/ModInt.hpp*/
/*<head>*/
# pragma once
/*</head>*/
# include <utility>
/**
* @file ModInt.hpp
* @brief mod構造体
* @author btk15049
* @date 2019/03/08
* @details
* \todo verifyが足りない
* verify: CSA12E，RUPC day3 F
*/
//! [WARNING!] mod が入力で与えられる場合はconstexprを外す
# ifdef STATIC_MOD
constexpr int mod = STATIC_MOD;
# else
int mod;
# endif
/**
* @brief mod構造体
* @details
* 整数をラップして，常に保持されているデータがmodされた状態になるよう管理．
*/
class ModInt {
private:
//! 中身
int x;
public:
/**
* @brief ゲッター
* @details 出力時などは "cout << *ret << endl;"のようにやるとよい．
*/
long long operator*() const { return x; }
/**
* @brief デフォルトコンストラクタ．0で初期化される．
*/
ModInt() { x = 0; }
/**
* @brief intからのコンストラクタ
* @param[in] y 設定したい値
* @details
* modをとらないので高速．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
ModInt(const int y) { x = y; }
/**
* @brief long longからのコンストラクタ
* @param[in] y 設定したい値
* @details 毎回modを取るので低速．
*/
ModInt(const long long y) { x = (int)((mod + y % mod) % mod); }
/**
* @brief ModIntからの代入演算子
* @param[in] o 設定したい値
* @details 高速
*/
ModInt(const ModInt& o) { this->x = *o; }
/**
* @brief 整数から高速にModIntを作りたいときに使う
* @param[in] x 設定したい値
* @details xが[0,mod)であることが保証されてないと正しく動かない．
*/
static inline ModInt raw(const long long x) {
// assert(x<mod);
return ModInt((int)x);
}
/**
* @brief 整数から安全にModIntを作りたいときに使う
* @param[in] x 設定したい値
* @details mod2回取るから遅い．負数でもOK．
*/
static inline ModInt get(const long long x) { return ModInt(x); }
/**
* @brief intからの代入演算子
* @param[in] o 設定したい値
* @details
* modをとらないので高速．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
ModInt& operator=(const int o) {
this->x = o >= mod ? o - mod : o;
return *this;
}
/**
* @brief long longからの代入演算子
* @param[in] o 設定したい値
* @details mod2回取るから遅い．負数でもOK．
*/
ModInt& operator=(const long long o) {
this->x = (int)((mod + o % mod) % mod);
return *this;
}
/**
* @brief ModIntからの代入演算子
* @param[in] o 設定したい値
* @details 高速
*/
ModInt& operator=(const ModInt o) {
this->x = *o;
return *this;
}
};
/**
* @param[in] l ModInt
* @param[in] r ModInt
* @details if文使って少し高速化．
*/
inline ModInt add(const ModInt l, const ModInt r) {
const long long x = *l + *r;
return ModInt::raw(x >= mod ? x - mod : x);
}
/**
* @param[in] l ModInt
* @param[in] r ModInt．
*/
inline ModInt mul(const ModInt l, const ModInt r) {
return ModInt::raw(*l * *r % mod);
}
/**
* @brief a^x %modを求める
* @param[in] a ModInt
* @param[in] x long long．
*/
inline ModInt pow(ModInt a, long long x) {
ModInt ret = ModInt::raw(1);
while (x) {
if (x & 1) {
ret = mul(ret, a);
}
a = mul(a, a);
x >>= 1;
}
return ret;
}
/**
* @brief x^-1 %modを求める
* @param[in] x ModInt．
* @details
* 内部ではユークリッドの拡張互助法を使っている．
* O(log(mod))
*/
inline ModInt inv(const ModInt x) {
long long a = *x, b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
std::swap(a -= t * b, b);
std::swap(u -= t * v, v);
}
return ModInt::get(u);
}
/**
* @brief 負数を求める単項演算子
* @param[in] x ModInt
*/
inline ModInt operator-(const ModInt x) { return add(mod, -*x); }
/**
* @param[in] l ModInt
* @param[in] r ModInt
*/
inline ModInt operator+(const ModInt l, const ModInt r) { return add(l, r); }
/**
* @param[in] l ModInt
* @param[in] r ModInt
*/
inline ModInt operator*(const ModInt l, const ModInt r) { return mul(l, r); }
/**
* @param[in] l ModInt
* @param[in] r ModInt
*/
inline ModInt operator-(const ModInt l, const ModInt r) { return add(l, -r); }
/**
* @param[in] l ModInt
* @param[in] r int
* @details
* 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
inline ModInt operator+(const ModInt l, const int r) {
return add(l, ModInt::raw(r));
}
/**
* @param[in] l ModInt
* @param[in] r int
*/
inline ModInt operator+(const ModInt l, const long long r) {
return add(l, ModInt::get(r));
}
/**
* @param[in] l ModInt
* @param[in] r int
* @details
* 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
inline ModInt operator*(const ModInt l, const int r) {
return mul(l, ModInt::raw(r));
}
/**
* @param[in] l ModInt
* @param[in] r int
*/
inline ModInt operator*(const ModInt l, const long long r) {
return mul(l, ModInt::get(r));
}
/**
* @param[in] l ModInt
* @param[in] r int
* @details
* 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
inline ModInt operator-(const ModInt l, const int r) {
return add(l, ModInt::raw(mod - r));
}
/**
* @param[in] l ModInt
* @param[in] r int
*/
inline ModInt operator-(const ModInt l, const long long r) {
return add(l, -ModInt::get(r));
}
/**
* @param[in] l ModInt
* @param[in] r int
* @details
* 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している．ただしmodより大きい値や負の数を入れると事故るので注意．
*/
inline ModInt operator/(const ModInt l, const int r) {
return mul(l, inv(ModInt::raw(r)));
}
/**
* @param[in] l ModInt
* @param[in] r int
*/
inline ModInt operator/(const ModInt l, const long long r) {
return mul(l, inv(ModInt::get(r)));
}
/**
* @param[in] l ModInt
* @param[in] r long long
* @details
* pow(l,r)を呼び出すだけなのでpowを参照のこと．
計算量はO(log mod)
*/
inline ModInt operator^(const ModInt l, const long long r) { return pow(l, r); }
/**
* @brief
* +=の実装、各operator+を呼ぶだけ
* @tparam T
* @param l ModInt
* @param r 足すやつ
* @return ModInt&
*/
template <typename T>
ModInt& operator+=(ModInt& l, T r) {
l = l + r;
return l;
}
/**
* @brief
* -=の実装、各operator-を呼ぶだけ
* @tparam T
* @param l ModInt
* @param r 引くやつ
* @return ModInt&
*/
template <typename T>
ModInt& operator-=(ModInt& l, T r) {
l = l - r;
return l;
}
/**
* @brief
* *=の実装、各operator*を呼ぶだけ
* @tparam T
* @param l ModInt
* @param r かけるやつ
* @return ModInt&
*/
template <typename T>
ModInt& operator*=(ModInt& l, T r) {
l = l * r;
return l;
}
/**
* @namespace factorial
* @brief 順列数関連の関数のまとめ
* @details
* - combination
* - permutation
* - multiChoose
*/
namespace factorial {
//! 順列数を格納する配列のサイズ
constexpr int size =
# ifdef FACTORIAL_SIZE
FACTORIAL_SIZE;
# else
3123456;
# endif
//! 前計算ができているかどうかのフラグ
bool is_build = false;
//! 順列数を格納する配列
ModInt factorial[size];
//! (順列数)^-1を格納する配列
ModInt inverse_factorial[size];
/**
* @brief 順列数の前計算
* @details
* 順列数と，その逆元を[0,size)まで求める.
* 計算量は，O(size + log(mod))
*/
void build() {
is_build = true;
factorial[0] = 1;
for (int i = 1; i < size; i++) {
factorial[i] = factorial[i - 1] * i;
}
inverse_factorial[size - 1] = inv(factorial[size - 1]);
for (int i = size - 1; i >= 1; i--) {
inverse_factorial[i - 1] = inverse_factorial[i] * i;
}
}
/**
* @brief nPkを求める
* @details
* 前計算がしてあれば O(1)．前計算してない場合は is_build
* を読み取って前計算をする．
*/
inline ModInt permutation(int n, int k) {
if (k < 0 || k > n) return ModInt::raw(0);
if (!is_build) build();
return factorial[n] * inverse_factorial[n - k];
}
/**
* @brief nCkを求める
* @details
* 前計算がしてあれば O(1)．前計算してない場合は is_build
* を読み取って前計算をする．
*/
inline ModInt combination(int n, int k) {
if (k < 0 || k > n) return ModInt::raw(0);
if (!is_build) build();
return factorial[n] * inverse_factorial[k] * inverse_factorial[n - k];
}
/**
* @brief 重複組合せ
* @param n 何種類のものを
* @param r いくつ並べるか
* @return ModInt nHr
*/
ModInt multiChoose(int n, int r) {
if (n == 0 && r == 0) return ModInt::raw(1);
return combination(n + r - 1, r);
}
/**
* @brief 上限付き重複組合せ
* @details
* 包除原理を用いて，lim個以上の品物が1,2,...,i種類の場合を足したり引いたりしていく
* 計算量は O(min(n, r / lim))
* @param n 何種類のものを
* @param r いくつ並べるか
* @param lim 1種類のものを選べる上限
* @return ModInt
*/
ModInt multiChoose(int n, int r, int lim) {
ModInt ret = 0;
for (int i = 0; i <= n; i++) {
if (i * (lim + 1) > r) break;
ret += ((i & 1) ? mod - 1 : 1) * combination(n, i)
* multiChoose(n, r - i * (lim + 1));
}
return ret;
}
} // namespace factorial
/* #endregion */
/* #endregion */
/*</body>*/
#endif
int N;
LL A[212];
LL B[212];
int AI[212];
int BI[212];
LL latte[1123];
int malta = 0;
// 積分
// 定数部は0
vector<ModInt> up(vector<ModInt> v) {
for (int i : range(v.size())) {
v[i] = v[i] / (i + 1);
}
reverse(ALL(v));
v.push_back(ModInt(0));
reverse(ALL(v));
return v;
}
// 多項式にxを代入
ModInt assign(vector<ModInt> v, ModInt x) {
v = up(v);
ModInt xx = 1;
ModInt ret = 0;
for (auto& it : v) {
ret += it * xx;
xx *= x;
}
return ret;
}
vector<ModInt> ad(vector<ModInt> x, vector<ModInt> y) {
if (x.size() < y.size()) swap(x, y);
for (int i : range(y.size())) {
x[i] += y[i];
}
return x;
}
ostream& operator<<(ostream& os, vector<ModInt> a) {
os << "{";
for (auto& it : a) {
os << *it << ",";
}
os << "}";
return os;
}
int main() {
/* write here */
cin >> N;
for (int i : range(N)) {
cin >> A[i] >> B[i];
latte[malta++] = A[i];
latte[malta++] = B[i];
}
sort(latte, latte + malta);
malta = unique(latte, latte + malta) - latte;
for (int i : range(N)) {
AI[i] = lower_bound(latte, latte + malta, A[i]) - latte;
BI[i] = lower_bound(latte, latte + malta, B[i]) - latte;
}
vector<vector<ModInt>> dp(malta - 1);
{
const int bg = AI[0];
const int ed = BI[0];
ModInt p = ModInt(1) / (B[0] - A[0]);
for (int i : range(malta - 1)) {
if (bg <= i && i + 1 <= ed) {
dp[i] = {p};
}
else {
dp[i] = {ModInt(0)};
}
}
}
// for (int j : range(malta - 1)) {
// cerr << j << " " << dp[j] << endl;
//}
for (int i : range(1, N)) {
ModInt p = ModInt(1) / (B[i] - A[i]);
const int bg = AI[i];
const int ed = BI[i];
vector<vector<ModInt>> nxt(malta - 1);
// 増える
if (i % 2 == 1) {
ModInt C = 0;
for (int j : range(malta - 1)) {
// cerr << i << " " << j << " " << *C << endl;
if (bg <= j && j + 1 <= ed) {
nxt[j] = up(dp[j]);
nxt[j][0] -= assign(dp[j], ModInt(latte[j]));
nxt[j][0] += C;
for (auto& it : nxt[j]) it *= p;
}
else {
nxt[j] = {ModInt(0)};
}
C += assign(dp[j], ModInt(latte[j + 1]))
- assign(dp[j], ModInt(latte[j]));
}
}
// 減る
else {
ModInt C = 0;
for (int j : !range(malta - 1)) {
if (bg <= j && j + 1 <= ed) {
nxt[j] = up(dp[j]);
for (auto& it : nxt[j]) it = -it;
nxt[j][0] += assign(dp[j], ModInt(latte[j + 1]));
nxt[j][0] += C;
for (auto& it : nxt[j]) it *= p;
}
else {
nxt[j] = {ModInt(0)};
}
C += assign(dp[j], ModInt(latte[j + 1]))
- assign(dp[j], ModInt(latte[j]));
}
}
swap(dp, nxt);
// for (int j : range(malta - 1)) {
// cerr << j << " " << dp[j] << endl;
//}
}
ModInt ret = 0;
for (int i : range(malta - 1)) {
ret = ret + assign(dp[i], ModInt(latte[i + 1]))
- assign(dp[i], ModInt(latte[i]));
}
cout << *ret << endl;
return 0;
}