#1136469 (C++17) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: zoidzium
• 提出日時: 2025-11-27 00:48:45
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 26,458 bytes
• コンパイル時間: 2,369 ms
• コンパイル使用メモリ: 216,492 KB
• 実行使用メモリ: 813,952 KB
• 最終ジャッジ日時: 2025-11-27 00:48:51
• 合計ジャッジ時間: 4,660 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 2 WA * 1 MLE * 1 -- * 21

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

using xy = pair<ll, ll>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;

using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;
using vbs8 = vector<bs8>;
using vbs16 = vector<bs16>;
using vbs32 = vector<bs32>;
using vbs64 = vector<bs64>;

using vs = vector<string>;
using vvs = vector<vs>;

using ull = unsigned long long;
using vul = vector<ull>;

using vd = vector<double>;
using vvd = vector<vd>;

using coord = pair<double, double>;
using vcoord = vector<coord>;

#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;

/////////////////////////////////////////////////
namespace zz_print {
class dbg {
 public:
  static bool unprint;
  static string margin;
  static string separated;
  static string indentS;
  static int hierarchical;
  static int topHier;
  static int precision;
  static bool exponential;

  static void setFloat(const int& prec, const bool& expo) {
    precision = prec;
    exponential = expo;
  };

 private:
  static void ZOUT(const ll& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const ull& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const int& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const unsigned int& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const double& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const float& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const char& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const string& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const bs8& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const bs16& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const bs32& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  static void ZOUT(const bs64& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };
  template <typename T>
  static void ZOUT(const T& x, const bool& tail = false) {
    cout << x;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
  };

  static bool BRANKET_BEGIN(const char& c_L) {
    cout << c_L << margin;
    if (hierarchical > 0) {
      hierarchical--;
      indentS.push_back(' ');
      indentS += margin;
      cout << endl << indentS;
      return false;
    }
    return true;
  };
  static void BRANKET_END(const char& c_R, const bool& flat,
                          const bool& tail = false) {
    if (!flat) {
      rep(i, 1 + margin.size()) indentS.pop_back();
      cout << endl << indentS;
    }
    cout << c_R;
    if (tail) {
      cout << margin << flush;
    } else {
      cout << separated << flush;
    }
    if (!flat) {
      hierarchical++;
      if (hierarchical == topHier) cout << endl << indentS;
    }
  };

  template <typename Elm>
  static void ZOUT(const vector<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('[');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END(']', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const list<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('(');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END(')', flat, tail);
  };

  template <typename LftElm, typename RgtElm>
  static void ZOUT(const pair<LftElm, RgtElm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('<');

    ZOUT(x.first);
    if (!flat) cout << endl << indentS;
    ZOUT(x.second, true);

    BRANKET_END('>', flat, tail);
  };

  template <typename LftElm, typename RgtElm>
  static void ZOUT(const map<LftElm, RgtElm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename LftElm, typename RgtElm>
  static void ZOUT(const multimap<LftElm, RgtElm>& x,
                   const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename LftElm, typename RgtElm>
  static void ZOUT(const unordered_map<LftElm, RgtElm>& x,
                   const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename LftElm, typename RgtElm>
  static void ZOUT(const unordered_multimap<LftElm, RgtElm>& x,
                   const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };

  template <typename Elm>
  static void ZOUT(const set<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const multiset<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const unordered_set<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const unordered_multiset<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('{');

    ll I = 0;
    ll N = x.size() - 1;
    each(ite, x) {
      ZOUT(*ite, (I == N));
      if (!flat && I != N) cout << endl << indentS;
      I++;
    }

    BRANKET_END('}', flat, tail);
  };

  template <typename Elm>
  static void ZOUT(const stack<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('[');

    stack<Elm> y = x;
    while (!y.empty()) {
      ZOUT(y.top(), y.size() == 1);
      y.pop();
      if (!flat && !y.empty()) cout << endl << indentS;
    }

    BRANKET_END(')', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const queue<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('[');

    queue<Elm> y = x;
    while (!y.empty()) {
      ZOUT(y.front(), y.size() == 1);
      y.pop();
      if (!flat && !y.empty()) cout << endl << indentS;
    }

    BRANKET_END(')', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const priority_queue<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('[');

    priority_queue<Elm> y = x;
    while (!y.empty()) {
      ZOUT(y.top(), y.size() == 1);
      y.pop();
      if (!flat && !y.empty()) cout << endl << indentS;
    }

    BRANKET_END(')', flat, tail);
  };
  template <typename Elm>
  static void ZOUT(const deque<Elm>& x, const bool& tail = false) {
    bool flat = BRANKET_BEGIN('[');

    deque<Elm> y = x;
    while (!y.empty()) {
      ZOUT(y.front(), y.size() == 1);
      y.pop_front();
      if (!flat && !y.empty()) cout << endl << indentS;
    }

    BRANKET_END(']', flat, tail);
  };

  static void ZOUT_BRANCH() {}
  template <typename HeadArg, typename... Args>
  static void ZOUT_BRANCH(HeadArg&& head, Args&&... args) {
    ZOUT(head);
    ZOUT_BRANCH(forward<Args>(args)...);
  };

 public:
  template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
  static void zout(Args&&... args) {
    if (unprint) return;
    margin = string(mgn, ' ');
    separated = string(sep, ' ');
    hierarchical = hier;
    topHier = hier;
    indentS = "";
    cout << setprecision(precision);
    if (exponential) {
      cout << scientific;
    } else {
      cout << fixed;
    }

    ZOUT_BRANCH(forward<Args>(args)...);

    cout << endl << defaultfloat;
  };
};

bool dbg::unprint = false;
string dbg::margin = "";
string dbg::separated = "";
string dbg::indentS = "";
int dbg::hierarchical = 0;
int dbg::topHier = 0;
int dbg::precision = 6;
bool dbg::exponential = false;

};  // namespace zz_print
using namespace zz_print;

namespace zz_time {
/// @brief プログラム実行時のタイムポイント
std::chrono::_V2::system_clock::time_point START_TIME =
    std::chrono::system_clock::now();
/// @brief プログラム実行から経過時間をミリ秒で取得
/// @param st 経過開始時刻(基本引数指定する必要なし)
/// @return 経過時間ミリ秒
ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) {
  std::chrono::_V2::system_clock::time_point now =
      std::chrono::system_clock::now();
  return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st)
                  .count());
};
/// @brief 実行時間が超過していないかの判定
/// @param mSec 実行時間制約ミリ秒
/// @return 実行時間制約以下であればtrue,その他はfalse
bool punctualityTime(const ll& mSec) { return (currentTime() < mSec); }

/// @brief 実行時間が超過しているかの判定
/// @param mSec 実行時間制約ミリ秒
/// @return 実行時間制約超過していればtrue,その他はfalse
bool spendTime(const ll& mSec) { return (currentTime() >= mSec); }
};  // namespace zz_time
using namespace zz_time;

namespace zz_random {
random_device seed_gen;
default_random_engine RANDOM_ENGINE(seed_gen());

/// @brief 整数閉区間[L,R]一様ランダム器生成
/// @param L 下限値 (default 0)
/// @param R 上限値 (default 1)
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
uniform_int_distribution<> createIntCloseSegRandom(const ll& L = 0,
                                                   const ll& R = 1) {
  return uniform_int_distribution<>(L, R);
};

/// @brief 実数閉区間[L,R]一様ランダム器生成
/// @param L 下限値 (default 0.0)
/// @param R 上限値 (default 1.0)
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
uniform_real_distribution<> createRealCloseSegRandom(const double& L = 0.0,
                                                     const double& R = 1.0) {
  return uniform_real_distribution<>(L, R);
};

/// @brief 正規表現ランダム器生成
/// @param average 平均値
/// @param s 標準偏差
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
normal_distribution<> createNormalRandom(const double& average = 0.0,
                                         const double& s = 1.0) {
  return normal_distribution<>(average, s);
};

};  // namespace zz_random
using namespace zz_random;

namespace zz_mod {
vl gcd(const ll& a, const ll& b) {
  if (a > b) {
    vl ans = gcd(b, a);
    return vl{ans[1], ans[0], ans[2]};
  }

  // |a 0| |X|   |b%a 0||      Y      |
  // |0 b| |Y| = |0   a||X+floor(b/a)Y| = gcd(a,b)
  //
  //          |X|   |-floor(b/a) 1|
  // F(a,b) = |Y| = |     1      0| F(b%a,a)
  if (a == 0) return vl{0, 1, b};
  vl ans = gcd(b % a, a);
  ans = vl{-(b / a) * ans[0] + ans[1], ans[0], ans[2]};

  if (a == b && ans[0] > ans[1]) swap(ans[0], ans[1]);
  return ans;
};

class pp {
 public:
  ll val;
  ll mod;
  static bool ignorePPModPrint;

  void recalc() {
    val %= mod;
    if (val < 0) val += mod;
  };

  /// @brief modint (+-*/ != exp ~ inv recalc )
  /// @param x value
  /// @param y mod (default= 998244353)
  pp(const ll& x = 0, const ll& y = 998244353) {
    val = x;
    mod = y;
    recalc();
  };

  friend pp operator+(const pp& x, const pp& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp&& x, const pp& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp& x, const pp&& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp&& x, const pp&& y) {
    return pp(x.val + y.val, x.mod);
  };

  template <typename T>
  friend pp operator+(const pp& x, const T& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp&& x, const T& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp& x, const T&& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp&& x, const T&& y) {
    return pp(x.val + y, x.mod);
  };

  friend pp operator-(const pp& x) { return pp(-x.val, x.mod); };
  friend pp operator-(const pp&& x) { return pp(-x.val, x.mod); };

  friend pp operator-(const pp& x, const pp& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp&& x, const pp& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp& x, const pp&& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp&& x, const pp&& y) {
    return pp(x.val - y.val, x.mod);
  };

  template <typename T>
  friend pp operator-(const pp& x, const T& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp&& x, const T& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp& x, const T&& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp&& x, const T&& y) {
    return pp(x.val - y, x.mod);
  };

  friend pp operator*(const pp& x, const pp& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp&& x, const pp& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp& x, const pp&& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp&& x, const pp&& y) {
    return pp(x.val * y.val, x.mod);
  };

  template <typename T>
  friend pp operator*(const pp& x, const T& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp&& x, const T& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp& x, const T&& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp&& x, const T&& y) {
    return pp(x.val * y, x.mod);
  };

  friend pp operator~(const pp& x) { return pp{gcd(x.val, x.mod)[0], x.mod}; }
  friend pp operator~(const pp&& x) { return pp{gcd(x.val, x.mod)[0], x.mod}; }

  friend pp operator/(const pp& x, const pp& y) { return x * (~y); };
  friend pp operator/(const pp&& x, const pp& y) { return x * (~y); };
  friend pp operator/(const pp& x, const pp&& y) { return x * (~y); };
  friend pp operator/(const pp&& x, const pp&& y) { return x * (~y); };

  template <typename T>
  friend pp operator/(const pp& x, const T& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp&& x, const T& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp& x, const T&& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp&& x, const T&& y) {
    return x * pp(y, x.mod).inv();
  };

  friend pp& operator+=(pp& x, const pp& y) {
    x.val += y.val;
    x.recalc();
    return x;
  };
  friend pp& operator+=(pp& x, const pp&& y) {
    x.val += y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator+=(pp& x, const T& y) {
    x.val += y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator+=(pp& x, const T&& y) {
    x.val += y;
    x.recalc();
    return x;
  };

  friend pp& operator-=(pp& x, const pp& y) {
    x.val -= y.val;
    x.recalc();
    return x;
  };
  friend pp& operator-=(pp& x, const pp&& y) {
    x.val -= y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator-=(pp& x, const T& y) {
    x.val -= y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator-=(pp& x, const T&& y) {
    x.val -= y;
    x.recalc();
    return x;
  };

  friend pp& operator*=(pp& x, const pp& y) {
    x.val *= y.val;
    x.recalc();
    return x;
  };
  friend pp& operator*=(pp& x, const pp&& y) {
    x.val *= y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator*=(pp& x, const T& y) {
    x.val *= y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator*=(pp& x, const T&& y) {
    x.val *= y;
    x.recalc();
    return x;
  };

  friend pp& operator/=(pp& x, const pp& y) {
    x *= pp(y.val, x.mod).inv();
    x.recalc();
    return x;
  };
  friend pp& operator/=(pp& x, const pp&& y) {
    x *= pp(y.val, x.mod).inv();
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator/=(pp& x, const T& y) {
    x *= pp(y, x.mod).inv();
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator/=(pp& x, const T&& y) {
    x *= pp(y, x.mod).inv();
    x.recalc();
    return x;
  };

  pp inv() const { return ~(*this); }

  pp exp(ll x) const {
    if (x == 0) {
      return pp(1, this->mod);
    }
    pp y = *this;

    if (x > 0) {
      vl Vec;
      while (x > 0) {
        Vec.push_back(x & 1);
        x >>= 1;
      }
      pp ans(1, this->mod);
      each(ite, Vec) {
        if (*ite) ans = ans * y;
        y = y * y;
      }

      return ans;
    }

    return y.inv().exp(-x);
  };

  friend ostream& operator<<(ostream& os, const pp& x) {
    if (ignorePPModPrint) {
      os << "{" << x.val << "}";
    } else {
      os << "{" << x.val << " %" << x.mod << "}";
    }
    return os;
  };
};
bool pp::ignorePPModPrint = false;

pp ganner(const vector<pp>& vec) {
  dbg::zout(" GANNER vec=", vec);
  pp ans = vec[0];
  cnt(i, 1, vec.size() - 1) {
    ll p1 = ans.mod, p2 = vec[i].mod, r1 = ans.val, r2 = vec[i].val;
    if (pp(r1, __gcd(p1, p2)).val != pp(r2, __gcd(p1, p2)).val) return pp(0, 1);
    vl xyd = gcd(p1, p2);
    // ans.mod = p1 * p2;
    // ans.val = r2 * p1 * xyd[0] + r1 * p2 * xyd[1];
    // ans = pp{r2 * p1, p1 * p2 / __gcd(p1, p2)} * xyd[0] * xyd[2];
    // ans += pp{r1 * p2, p1 * p2 / __gcd(p1, p2)} * xyd[1] * xyd[2];
    ll M = p1 * p2 / __gcd(p1, p2);
    ans = pp{(r2 - r1) / xyd[2], M} * p1 * xyd[0] + r1;

    dbg::zout(" i=", i, " xyd=", xyd, " ans=", ans);
  }

  return ans;
}

class factorial {
 public:
  const ll size;
  vector<pp> vec;
  /// @brief mod! (operator[] comb)
  /// @param x max! [0,x]  (default 1000000)
  /// @param y mod (default 998244353)
  factorial(const ll&& x = 1000000, const ll&& y = 998244353) : size(x + 1) {
    vec = vector<pp>(x + 1, pp(1, y));
    cnt(i, 2, x) vec[i] *= (vec[i - 1] * pp(i, y));
  };

  /// @brief mod factorial
  /// @return x! mod
  pp operator[](const ll& x) const { return vec[x]; };

  /// @brief mod factorial
  /// @return x! mod
  pp operator[](const ll&& x) const { return vec[x]; };

  /// @brief mod combination
  /// @param n
  /// @param m
  /// @return nCm
  pp comb(const ll n, const ll m) const {
    return (vec[n] / (vec[m] * vec[n - m]));
  };
};

class convolution {
 public:
  vector<pp> vec;
  vector<pp> VEC;
  pp zeta;
  ll bsize;
  pp zeta_init;
  ll bsize_Lmt;
  const ll type;

  void resize(const ll& n = -1) {
    if (n >= 0) {
      bsize = n;
    } else {
      bsize = 0;
      while (vec.size() > (1LL << bsize)) bsize++;
    }
    zeta = zeta_init;
    rep(i, bsize_Lmt - bsize) zeta *= zeta;

    if (vec.size() >= (1LL << bsize)) {
      vec.resize(1LL << bsize);
      VEC.resize(1LL << bsize);
    } else {
      while (vec.size() < (1LL << bsize)) {
        vec.push_back(pp{0, zeta_init.mod});
        VEC.push_back(pp{0, zeta_init.mod});
      }
    }
  };

  void init() {
    switch (type) {
      case 3:
        zeta_init = pp(26, 880803841).exp(105);
        bsize_Lmt = 23;
        break;
      case 2:
        zeta_init = pp(3, 897581057).exp(107);
        bsize_Lmt = 23;
        break;
      case 1:
        zeta_init = pp(7, 377487361).exp(45);
        bsize_Lmt = 23;
        break;
      case 0:
      default:
        zeta_init = pp(3, 998244353).exp(119);
        bsize_Lmt = 23;
        break;
    }
  }

  convolution(const ll& t = 0) : type(t) {
    init();
    resize();
  }

  convolution(const vl& v, const ll& t = 0) : type(t) {
    init();
    vec.clear();
    each(ite, v) vec.push_back(pp{*ite, zeta_init.mod});
    resize();
  }

  convolution(const vector<pp>& v, const ll& t = 0) : type(t) {
    init();
    vec.clear();
    each(ite, v) vec.push_back(pp{ite->val, zeta_init.mod});
    resize();
  }

  void FFT() {
    resize();
    VEC = transform(vec, zeta);
  }

  void RFFT() {
    resize();
    vec = transform(VEC, zeta.inv());
    rep(i, vec.size()) vec[i] /= vec.size();
  }

  void CONV(convolution& a, convolution& b) {
    ll d = max<ll>(a.bsize, b.bsize) + 1;
    a.resize(d);
    b.resize(d);

    a.FFT();
    b.FFT();

    resize(d);
    rep(i, VEC.size()) VEC[i] = a.VEC[i] * b.VEC[i];
    RFFT();
    rep(i, VEC.size()) VEC[i] /= VEC.size();
  }

  void CONV(const vl& va, const vl& vb) {
    convolution a(va, type);
    convolution b(vb, type);
    CONV(a, b);
  }

  vector<pp> transform(const vector<pp>& v, const pp& z) {
    ll n = v.size();
    if (n == 1) return v;
    vector<pp> sub1(n / 2, pp{0, zeta_init.mod}),
        sub2(n / 2, pp{0, zeta_init.mod});

    rep(i, n / 2) {
      sub1[i] = v[2 * i];
      sub2[i] = v[2 * i + 1];
    }
    vector<pp> SUB1, SUB2;
    SUB1 = transform(sub1, z * z);
    SUB2 = transform(sub2, z * z);
    vector<pp> ans(n);

    pp w = pp{1, z.mod};

    rep(i, n) {
      ans[i] = SUB1[i % (n / 2)] + SUB2[i % (n / 2)] * w;
      w *= z;
    }
    return ans;
  }

  static vector<pp> CONV_vp(const vl& va, const vl& vb, const ll& mod = -1) {
    vector<convolution> c;
    rep(i, 2) {
      c.push_back(convolution(i));
      c[i].CONV(va, vb);
      dbg::zout(c[i].vec);
    }
    vector<pp> ans;
    ll n = c[0].vec.size();
    if (mod <= 0) {
      rep(i, n) ans.push_back(ganner(vector<pp>{c[0].vec[i], c[1].vec[i]}));
    } else {
      rep(i, n) ans.push_back(
          pp{ganner(vector<pp>{c[0].vec[i], c[1].vec[i]}).val, mod});
    }
    return ans;
  }
};

};  // namespace zz_mod
using namespace zz_mod;

namespace zz_algorithm {
vl quotients(const ll& N) {
  vl ans(1, 1);
  ll add = 1;
  ll q = N;
  while (q > 1) {
    // same [L R) less than
    ll L = add, R = N + 1;
    while ((L + 1) < R) {
      ll C = (L + R) / 2;
      if (q == (N / C)) {
        L = C;
      } else {
        R = C;
      }
    }
    add = L + 1;
    q = N / add;
    ans.push_back(add);
  }
  return ans;
};

bool permutation(vl& vec) {
  ll N = vec.size();
  if (N == 1) {
    return false;
  };
  if (N == 2) {
    if (vec[0] > vec[1]) {
      swap(vec[0], vec[1]);
      return true;
    }
    return false;
  }

  ll L = N - 1, R = N;
  rcnt(i, N - 1, 1) {
    if (vec[i - 1] < vec[i]) {
      break;
    }
    L--;
  }
  if (L == 0) {
    return false;
  }

  ll I = L - 1;
  if (vec[I] < vec[R - 1]) L = R - 1;
  while ((L + 1) < R) {
    ll C = (L + R) / 2;
    if (vec[I] < vec[C]) {
      L = C;
    } else {
      R = C;
    }
  }
  swap(vec[I], vec[L]);
  ll j = N - 1;
  cnt(i, I + 1, N - 1) {
    if (i >= j) break;
    swap(vec[i], vec[j]);
    j--;
  }
  return true;
};
}  // namespace zz_algorithm
using namespace zz_algorithm;
/////////////////////////////////////////////////

/////////////////////////////////////////////////

int main() {
  dbg::unprint = true;

  // ll N, M;
  // cin >> N >> M;
  // vl A(N), B(M);
  // rep(i, N) cin >> A[i];
  // rep(i, M) cin >> B[i];

  // // vector<pp> C = convolution::CONV_vp(A, B, 998244353);
  // vector<pp> C = convolution::CONV_vp(A, B, 1000000007);
  // dbg::zout(C);
  // rep(i, N + M - 1) cout << C[i].val << " ";
  // cout << endl;

  ll N;
  cin >> N;
  vl X(N), Y(N);
  rep(i, N) cin >> X[i] >> Y[i];

  vector<pp> VP;
  rep(i, N) VP.push_back(pp(X[i], Y[i]));
  pp A = ganner(VP);
  if (A.mod == 1) {
    cout << -1 << endl;
    return 0;
  }
  cout << pp(A.val, 1000000007).val << endl;
  return 0;
}