結果
問題 | No.2580 Hyperinflation |
ユーザー |
|
提出日時 | 2023-12-08 01:00:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 33,845 bytes |
コンパイル時間 | 6,011 ms |
コンパイル使用メモリ | 218,932 KB |
実行使用メモリ | 106,496 KB |
最終ジャッジ日時 | 2024-09-27 02:31:20 |
合計ジャッジ時間 | 23,495 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 TLE * 1 -- * 10 |
ソースコード
// N^3#include <bit>#include <iostream>#include <vector>#include <atcoder/modint>#include <atcoder/convolution>using mint = atcoder::modint998244353;#include <cassert>#include <vector>#include <iomanip>#include <iostream>#include <sstream>#include <vector>#include <atcoder/convolution>namespace suisen::internal {template <typename T, typename R = T>std::vector<R> convolution_naive(const std::vector<T>& a, const std::vector<T>& b) {const int n = a.size(), m = b.size();std::vector<R> c(n + m - 1);if (n < m) {for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) c[i + j] += R(a[i]) * b[j];} else {for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i + j] += R(a[i]) * b[j];}return c;}} // namespace suisennamespace suisen {template <typename mint, atcoder::internal::is_modint_t<mint>* = nullptr>std::vector<mint> arbitrary_mod_convolution(const std::vector<mint>& a, const std::vector<mint>& b) {int n = int(a.size()), m = int(b.size());if constexpr (atcoder::internal::is_static_modint<mint>::value) {int maxz = 1;while (not ((mint::mod() - 1) & maxz)) maxz <<= 1;int z = 1;while (z < n + m - 1) z <<= 1;if (z <= maxz) return atcoder::convolution<mint>(a, b);}if (n == 0 or m == 0) return {};if (std::min(n, m) <= 120) return internal::convolution_naive(a, b);static constexpr long long MOD1 = 754974721; // 2^24static constexpr long long MOD2 = 167772161; // 2^25static constexpr long long MOD3 = 469762049; // 2^26static constexpr long long M1M2 = MOD1 * MOD2;static constexpr long long INV_M1_MOD2 = atcoder::internal::inv_gcd(MOD1, MOD2).second;static constexpr long long INV_M1M2_MOD3 = atcoder::internal::inv_gcd(M1M2, MOD3).second;std::vector<int> a2(n), b2(m);for (int i = 0; i < n; ++i) a2[i] = a[i].val();for (int i = 0; i < m; ++i) b2[i] = b[i].val();auto c1 = atcoder::convolution<MOD1>(a2, b2);auto c2 = atcoder::convolution<MOD2>(a2, b2);auto c3 = atcoder::convolution<MOD3>(a2, b2);const long long m1m2 = mint(M1M2).val();std::vector<mint> c(n + m - 1);for (int i = 0; i < n + m - 1; ++i) {// Garner's Algorithm// X = x1 + x2 * m1 + x3 * m1 * m2// x1 = c1[i], x2 = (c2[i] - x1) / m1 (mod m2), x3 = (c3[i] - x1 - x2 * m1) / m2 (mod m3)long long x1 = c1[i];long long x2 = (atcoder::static_modint<MOD2>(c2[i] - x1) * INV_M1_MOD2).val();long long x3 = (atcoder::static_modint<MOD3>(c3[i] - x1 - x2 * MOD1) * INV_M1M2_MOD3).val();c[i] = x1 + x2 * MOD1 + x3 * m1m2;}return c;}std::vector<__uint128_t> convolution_int(const std::vector<int> &a, const std::vector<int> &b) {int n = int(a.size()), m = int(b.size());auto check_nonnegative = [](int e) { return e >= 0; };assert(std::all_of(a.begin(), a.end(), check_nonnegative));assert(std::all_of(b.begin(), b.end(), check_nonnegative));if (n == 0 or m == 0) return {};if (std::min(n, m) <= 120) return internal::convolution_naive<int, __uint128_t>(a, b);static constexpr long long MOD1 = 754974721; // 2^24static constexpr long long MOD2 = 167772161; // 2^25static constexpr long long MOD3 = 469762049; // 2^26static constexpr long long M1M2 = MOD1 * MOD2;static constexpr long long INV_M1_MOD2 = atcoder::internal::inv_gcd(MOD1, MOD2).second;static constexpr long long INV_M1M2_MOD3 = atcoder::internal::inv_gcd(M1M2, MOD3).second;auto c1 = atcoder::convolution<MOD1>(a, b);auto c2 = atcoder::convolution<MOD2>(a, b);auto c3 = atcoder::convolution<MOD3>(a, b);std::vector<__uint128_t> c(n + m - 1);for (int i = 0; i < n + m - 1; ++i) {// Garner's Algorithm// X = x1 + x2 * m1 + x3 * m1 * m2// x1 = c1[i], x2 = (c2[i] - x1) / m1 (mod m2), x3 = (c3[i] - x1 - x2 * m1) / m2 (mod m3)int x1 = c1[i];int x2 = (atcoder::static_modint<MOD2>(c2[i] - x1) * INV_M1_MOD2).val();int x3 = (atcoder::static_modint<MOD3>(c3[i] - x1 - x2 * MOD1) * INV_M1M2_MOD3).val();c[i] = x1 + x2 * MOD1 + __uint128_t(x3) * M1M2;}return c;}} // namespace suisennamespace suisen {struct unsigned_bigint : private std::vector<int> {static constexpr int D = 1000000000;static constexpr int LogD = 9;static inline struct { operator unsigned_bigint() const { return unsigned_bigint{}; }; } const ZERO{};static inline struct { operator unsigned_bigint() const { return unsigned_bigint{ 1 }; }; } const ONE{};unsigned_bigint() : vector() {}template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>unsigned_bigint(T v) {if constexpr (std::is_signed_v<T>) {assert(v >= 0);}for (; v; v /= D) {this->push_back(v % D);}}unsigned_bigint(const std::string& s) : vector() {int siz = s.size();for (int i = siz; i > 0; i -= LogD) {int l = std::max(0, i - LogD);int r = i;int& v = this->emplace_back();for (int j = l; j < r; ++j) {int d = s[j] - '0';assert(0 <= d and d <= 9);v = v * 10 + d;}}}unsigned_bigint(const char* s) : unsigned_bigint(std::string(s)) {}operator bool() const {return not this->empty();}friend bool operator==(const unsigned_bigint& a, const unsigned_bigint& b) {if (a.size() != b.size()) {return false;}for (size_t i = 0; i < a.size(); ++i) {if (a[i] != b[i]) return false;}return true;}friend bool operator!=(const unsigned_bigint& a, const unsigned_bigint& b) {return not (a == b);}friend bool operator<(const unsigned_bigint& a, const unsigned_bigint& b) {if (a.size() != b.size()) {return a.size() < b.size();}for (size_t i = a.size(); i-- > 0;) {if (a[i] != b[i]) return a[i] < b[i];}return false;}friend bool operator<=(const unsigned_bigint& a, const unsigned_bigint& b) {return not (b < a);}friend bool operator>(const unsigned_bigint& a, const unsigned_bigint& b) {return b < a;}friend bool operator>=(const unsigned_bigint& a, const unsigned_bigint& b) {return not (a < b);}friend unsigned_bigint& operator<<=(unsigned_bigint& a, int shamt) {if (a) a.insert(a.begin(), shamt, 0);return a;}friend unsigned_bigint operator<<(unsigned_bigint a, int shamt) {a <<= shamt;return a;}friend unsigned_bigint& operator>>=(unsigned_bigint& a, int shamt) {a.erase(a.begin(), a.begin() + std::min<int>(shamt, a.size()));return a;}friend unsigned_bigint operator>>(unsigned_bigint a, int shamt) {a >>= shamt;return a;}unsigned_bigint& operator++() {return _incr_assign(*this);}unsigned_bigint operator++(int) {unsigned_bigint res = *this;_incr_assign(*this);return res;}unsigned_bigint& operator--() {return _decr_assign(*this);}unsigned_bigint operator--(int) {unsigned_bigint res = *this;_decr_assign(*this);return res;}friend unsigned_bigint& operator+=(unsigned_bigint& a, const unsigned_bigint& b) {return _add_assign(a, b);}friend unsigned_bigint operator+(const unsigned_bigint& a, const unsigned_bigint& b) {unsigned_bigint c = a;c += b;return c;}friend unsigned_bigint& operator-=(unsigned_bigint& a, const unsigned_bigint& b) {return _sub_assign(a, b);}friend unsigned_bigint operator-(const unsigned_bigint& a, const unsigned_bigint& b) {unsigned_bigint c = a;c -= b;return c;}friend unsigned_bigint& operator*=(unsigned_bigint& a, const unsigned_bigint& b) {return a = a * b;}friend unsigned_bigint operator*(const unsigned_bigint& a, const unsigned_bigint& b) {return _mul_fft(a, b);}static std::pair<unsigned_bigint, unsigned_bigint> divmod(unsigned_bigint a, unsigned_bigint b) {return _divmod(a, b);}friend unsigned_bigint& operator/=(unsigned_bigint& a, const unsigned_bigint& b) {return a = a / b;}friend unsigned_bigint operator/(const unsigned_bigint& a, const unsigned_bigint& b) {return divmod(a, b).first;}friend unsigned_bigint& operator%=(unsigned_bigint& a, const unsigned_bigint& b) {return a = a % b;}friend unsigned_bigint operator%(const unsigned_bigint& a, const unsigned_bigint& b) {return divmod(a, b).second;}#define CAST_PRIMITIVE(type) \operator type() const { \type res = 0; \for (auto it = this->rbegin(); it != this->rend(); ++it) { \res = res * D + *it; \} \return res; \} \CAST_PRIMITIVE(unsigned int)CAST_PRIMITIVE(unsigned long)CAST_PRIMITIVE(unsigned long long)CAST_PRIMITIVE(__uint128_t)CAST_PRIMITIVE(float)CAST_PRIMITIVE(double)CAST_PRIMITIVE(long double)#undef CAST_PRIMITIVE#define CAST_SIGNED_INT(type) \operator type() const { \return static_cast<std::make_unsigned_t<type>>(*this); \} \CAST_SIGNED_INT(int)CAST_SIGNED_INT(long)CAST_SIGNED_INT(long long)#undef CAST_SIGNED_INToperator __int128_t() const {return static_cast<__uint128_t>(*this);}operator std::string() const {return _to_string();}friend std::istream& operator>>(std::istream& in, unsigned_bigint& v) {std::string s;in >> s, v = s;return in;}friend std::ostream& operator<<(std::ostream& out, const unsigned_bigint& v) {return out << v._to_string();}private:using std::vector<int>::vector;void _check_leading_zeros() const {assert(this->empty() or this->back());}void _cut_leading_zeros() {while (this->size() and this->back() == 0) this->pop_back();}static unsigned_bigint& _incr_assign(unsigned_bigint& a) {for (int& e : a) {if (++e != D) return a;e -= D;}a.push_back(1);return a;}static unsigned_bigint& _decr_assign(unsigned_bigint& a) {assert(a.size());for (int& e : a) {if (--e >= 0) break;e += D;}a._cut_leading_zeros();return a;}static unsigned_bigint& _add_assign(unsigned_bigint& a, const unsigned_bigint& b) {if (a.size() < b.size()) a.resize(b.size());int carry = 0;for (size_t i = 0; i < a.size(); ++i) {if (i >= b.size()) {if (carry) {++a[i];} else break;} else {a[i] += b[i] + carry;}if (a[i] >= D) {a[i] -= D;carry = 1;} else {carry = 0;}}if (carry) a.push_back(1);return a;}static unsigned_bigint& _sub_assign(unsigned_bigint& a, const unsigned_bigint& b) {assert(a.size() >= b.size());int borrow = 0;for (size_t i = 0; i < a.size(); ++i) {if (i >= b.size()) {if (borrow) {--a[i];} else break;} else {a[i] -= b[i] + borrow;}if (a[i] < 0) {a[i] += D;borrow = 1;} else {borrow = 0;}}assert(not borrow);a._cut_leading_zeros();return a;}unsigned_bigint _cut(int l, int r) const {r = std::min(r, static_cast<int>(this->size()));unsigned_bigint v = l < r ? unsigned_bigint(this->begin() + l, this->begin() + r) : ZERO;v._cut_leading_zeros();return v;}template <typename T>static unsigned_bigint _build(const std::vector<T>& dat) {unsigned_bigint res;T carry = 0;for (auto v : dat) {carry += v;res.push_back(carry % D);carry /= D;}while (carry) {res.push_back(carry % D);carry /= D;}res._cut_leading_zeros();return res;}static unsigned_bigint _mul_naive(const unsigned_bigint& a, const unsigned_bigint& b) {return _build(suisen::internal::convolution_naive<int, __int128_t>(a, b));}static unsigned_bigint _mul_karatsuba(const unsigned_bigint& a, const unsigned_bigint& b) {if (std::min(a.size(), b.size()) <= 64) {return _mul_naive(a, b);}const int m = std::max(a.size(), b.size()) / 2;unsigned_bigint lo_a = a._cut(0, m), hi_a = a._cut(m, a.size());unsigned_bigint lo_b = b._cut(0, m), hi_b = b._cut(m, b.size());unsigned_bigint lo_c = lo_a * lo_b;unsigned_bigint hi_c = hi_a * hi_b;bool neg = true;unsigned_bigint md_a;if (hi_a >= lo_a) md_a = hi_a - lo_a;else md_a = lo_a - hi_a, neg = not neg;unsigned_bigint md_b;if (hi_b >= lo_b) md_b = hi_b - lo_b;else md_b = lo_b - hi_b, neg = not neg;unsigned_bigint md_ab = md_a * md_b;unsigned_bigint md_c = (hi_c << m) + lo_c + hi_c + lo_c._cut(m, lo_c.size());if (neg) md_c -= md_ab;else md_c += md_ab;unsigned_bigint c = (md_c << m) + lo_c._cut(0, m);c._cut_leading_zeros();return c;}static unsigned_bigint _mul_fft(const unsigned_bigint& a, const unsigned_bigint& b) {if (std::min(a.size(), b.size()) <= 64) {return _mul_naive(a, b);}if (std::max(a.size(), b.size()) <= 200) {return _mul_karatsuba(a, b);}return _build(suisen::convolution_int(a, b));}// compare(a, D^k)static int _compare_powD(const unsigned_bigint& a, int k) {const int dA = a.size();if (dA <= k) return -1;if (dA >= k + 2) return +1;if (a[k] != 1) return +1;for (int i = 0; i < k; ++i) {if (a[i]) return +1;}return 0;}static unsigned_bigint _powD(int k) {return ONE << k;}static std::pair<unsigned_bigint, unsigned_bigint> _divmod_int(const unsigned_bigint& a, const unsigned_bigint& b) {assert(b.size() == 1);const int b0 = b.front();unsigned_bigint q;long long r = 0;for (auto it = a.rbegin(); it != a.rend(); ++it) {r = r * D + *it;q.push_back(r / b0);r %= b0;}std::reverse(q.begin(), q.end());q._cut_leading_zeros();return { q, r ? unsigned_bigint{ int(r) } : ZERO };}static std::pair<unsigned_bigint, unsigned_bigint> _divmod_naive(unsigned_bigint& a, unsigned_bigint& b) {if (b.size() == 1) {return _divmod_int(a, b);}if (a < b) {return { ZERO, a };}const unsigned_bigint coef{ D / (b.back() + 1) };a *= coef;b *= coef;assert(2 * b.back() >= D);unsigned_bigint q, r(a.end() - b.size(), a.end());for (int i = a.size() - b.size(); i >= 0; --i) {if (r.size() < b.size()) {q.push_back(0);} else if (r.size() == b.size()) {if (r >= b) {q.push_back(1);r -= b;} else {q.push_back(0);}} else {assert(r.size() == b.size() + 1);int x = (static_cast<long long>(r.end()[-1]) * D + r.end()[-2]) / b.back();unsigned_bigint bx = b * unsigned_bigint{ x };while (bx > r) bx -= b, --x;while (bx + b <= r) bx += b, ++x;q.push_back(x);r = r - bx;}if (i) {r.insert(r.begin(), a[i - 1]);}}std::reverse(q.begin(), q.end());q._cut_leading_zeros();r._cut_leading_zeros();return { q, _divmod_int(r, coef).first };}static std::pair<unsigned_bigint, unsigned_bigint> _divmod_naive(const unsigned_bigint& a, const unsigned_bigint& b) {unsigned_bigint a_ = a, b_ = b;return _divmod_naive(a_, b_);}// floor(D^n/b)static unsigned_bigint _div_powD(int n, unsigned_bigint b) {assert(b.size() and 2 * b.back() >= D);const int dB = b.size();int k = n - dB;while (k > 64) k = (k + 1) >> 1;k = std::min(n, dB + k);unsigned_bigint c = _divmod_naive(_powD(k), b).first;unsigned_bigint bc = b * c;for (; k < n; k = 2 * k - dB) {// loop invariant: c = floor(D^k/B)bc.resize(k + 1);int carry = 0;for (int i = 0; i < k; ++i) {bc[i] = D - bc[i] + (i ? carry - 1 : 0);if (bc[i] >= D) {bc[i] -= D;carry = 1;} else {carry = 0;}}++bc[k];c *= bc;c.erase(c.begin(), c.begin() + dB);bc = b * c;if (_compare_powD(bc + b, 2 * k - dB) <= 0) {++c, bc += b;}assert(_compare_powD(bc + b, 2 * k - dB) > 0);}// c = floor(D^k/b)c >>= k - n;return c;}static std::pair<unsigned_bigint, unsigned_bigint> _divmod(unsigned_bigint a, unsigned_bigint b) {assert(b.size());if (std::min(static_cast<int>(b.size()), static_cast<int>(a.size()) - static_cast<int>(b.size())) <= 64) {return _divmod_naive(a, b);}if (a < b) {return { ZERO, a };}const unsigned_bigint coef{ D / (b.back() + 1) };a *= coef;b *= coef;assert(2 * b.back() >= D);const int dA = a.size(), dB = b.size();if (dA == dB) {return { ONE, _divmod_int(a - b, coef).first };}unsigned_bigint invB = _div_powD(dA, b);unsigned_bigint q = a * invB;q.erase(q.begin(), q.begin() + dA);unsigned_bigint qb = q * b, qb2 = qb + b;if (qb2 <= a) {return { ++q, _divmod_int(a - qb2, coef).first };} else {return { q, _divmod_int(a - qb, coef).first };}}std::string _to_string() const {if (this->empty()) return "0";std::ostringstream oss;auto it = this->rbegin();oss << *it;while (++it != this->rend()) {oss << std::setw(9) << std::setfill('0') << *it;}return oss.str();}};} // namespace suisennamespace suisen {struct bigint {static inline struct { operator bigint() const { return bigint{ unsigned_bigint::ZERO }; }; } const ZERO{};static inline struct { operator bigint() const { return bigint{ unsigned_bigint::ONE }; }; } const ONE{};bigint() : _neg(false), _dat{} {}template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>bigint(T v) {_neg = false;if constexpr (std::is_signed_v<T>) {if (v < 0) {_neg = true;v = -v;}}_dat = unsigned_bigint(v);}bigint(const std::string& s) {if (s.front() == '-') {_neg = true;_dat = unsigned_bigint(s.substr(1));fix_sign();} else {_neg = false;_dat = unsigned_bigint(s);}}bigint(const char* s) : bigint(std::string(s)) {}bigint(const unsigned_bigint& dat) : _neg(false), _dat(dat) {}bigint(unsigned_bigint&& dat) : _neg(false), _dat(std::move(dat)) {}operator bool() const {return bool(_dat);}friend bool operator==(const bigint& a, const bigint& b) {if (a._neg xor b._neg) {return false;} else {return a._dat == b._dat;}}friend bool operator!=(const bigint& a, const bigint& b) {return not (a == b);}friend bool operator<(const bigint& a, const bigint& b) {if (a._neg xor b._neg) {return a._neg;} else if (a._neg) {return a._dat > b._dat;} else {return a._dat < b._dat;}}friend bool operator<=(const bigint& a, const bigint& b) {return not (b < a);}friend bool operator>(const bigint& a, const bigint& b) {return b < a;}friend bool operator>=(const bigint& a, const bigint& b) {return not (a < b);}friend bigint& operator<<=(bigint& a, int shamt) {a._dat <<= shamt;return a;}friend bigint operator<<(bigint a, int shamt) {a <<= shamt;return a;}friend bigint& operator>>=(bigint& a, int shamt) {a._dat >>= shamt;a.fix_sign();return a;}friend bigint operator>>(bigint a, int shamt) {a >>= shamt;a.fix_sign();return a;}bigint operator+() const {return *this;}bigint operator-() const {return bigint(_dat, not _neg);}bigint& operator++() {if (_neg) {--_dat;fix_sign();} else {++_dat;}return *this;}bigint operator++(int) {bigint res = *this;++*this;return res;}bigint& operator--() {if (_neg) {++_dat;} else if (_dat) {--_dat;} else {_neg = true;_dat = unsigned_bigint::ONE;}return *this;}bigint operator--(int) {bigint res = *this;--*this;return res;}friend bigint& operator+=(bigint& a, const bigint& b) {if (a._neg xor b._neg) {if (a._dat >= b._dat) {a._dat -= b._dat;} else {a._dat = b._dat - a._dat;a._neg = not a._neg;}a.fix_sign();} else {a._dat += b._dat;}return a;}friend bigint operator+(const bigint& a, const bigint& b) {bigint c = a;c += b;return c;}friend bigint& operator-=(bigint& a, const bigint& b) {if (a._neg xor b._neg) {a._dat += b._dat;} else {if (a._dat >= b._dat) {a._dat -= b._dat;} else {a._dat = b._dat - a._dat;a._neg = not a._neg;}a.fix_sign();}return a;}friend bigint operator-(const bigint& a, const bigint& b) {bigint c = a;c -= b;return c;}friend bigint& operator*=(bigint& a, const bigint& b) {return a = a * b;}friend bigint operator*(const bigint& a, const bigint& b) {return bigint(a._dat * b._dat, a._neg xor b._neg);}static std::pair<bigint, bigint> divmod(bigint a, bigint b) {auto [q, r] = unsigned_bigint::divmod(a._dat, b._dat);return { bigint(std::move(q), a._neg xor b._neg), bigint(std::move(r), a._neg) };}friend bigint& operator/=(bigint& a, const bigint& b) {return a = a / b;}friend bigint operator/(const bigint& a, const bigint& b) {return divmod(a, b).first;}friend bigint& operator%=(bigint& a, const bigint& b) {return a = a % b;}friend bigint operator%(const bigint& a, const bigint& b) {return divmod(a, b).second;}#define CAST_PRIMITIVE(type) \operator type() const { \type res = _dat; \return _neg ? -res : res; \} \CAST_PRIMITIVE(unsigned int)CAST_PRIMITIVE(unsigned long)CAST_PRIMITIVE(unsigned long long)CAST_PRIMITIVE(__uint128_t)CAST_PRIMITIVE(float)CAST_PRIMITIVE(double)CAST_PRIMITIVE(long double)#undef CAST_PRIMITIVE#define CAST_SIGNED_INT(type) \operator type() const { \return static_cast<std::make_unsigned_t<type>>(*this); \} \CAST_SIGNED_INT(int)CAST_SIGNED_INT(long)CAST_SIGNED_INT(long long)#undef CAST_SIGNED_INToperator __int128_t() const {return static_cast<__uint128_t>(*this);}operator unsigned_bigint() const {assert(not _neg);return _dat;}operator std::string() const {if (_neg) {return '-' + std::string(_dat);} else {return std::string(_dat);}}friend std::istream& operator>>(std::istream& in, bigint& v) {std::string s;in >> s, v = s;return in;}friend std::ostream& operator<<(std::ostream& out, const bigint& v) {return out << std::string(v);}private:bigint(const unsigned_bigint& dat, bool neg) : _neg(neg), _dat(dat) { fix_sign(); }bigint(unsigned_bigint&& dat, bool neg) : _neg(neg), _dat(std::move(dat)) { fix_sign(); }bool _neg;unsigned_bigint _dat;void fix_sign() {if (_neg and not _dat) _neg = false;}};} // namespace suisen#include <cassert>namespace suisen {template <typename T, typename U = T>struct factorial {factorial() = default;factorial(int n) { ensure(n); }static void ensure(const int n) {int sz = _fac.size();if (n + 1 <= sz) return;int new_size = std::max(n + 1, sz * 2);_fac.resize(new_size), _fac_inv.resize(new_size);for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i;_fac_inv[new_size - 1] = U(1) / _fac[new_size - 1];for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i;}T fac(const int i) {ensure(i);return _fac[i];}T operator()(int i) {return fac(i);}U fac_inv(const int i) {ensure(i);return _fac_inv[i];}U binom(const int n, const int r) {if (n < 0 or r < 0 or n < r) return 0;ensure(n);return _fac[n] * _fac_inv[r] * _fac_inv[n - r];}template <typename ...Ds, std::enable_if_t<std::conjunction_v<std::is_integral<Ds>...>, std::nullptr_t> = nullptr>U polynom(const int n, const Ds& ...ds) {if (n < 0) return 0;ensure(n);int sumd = 0;U res = _fac[n];for (int d : { ds... }) {if (d < 0 or d > n) return 0;sumd += d;res *= _fac_inv[d];}if (sumd > n) return 0;res *= _fac_inv[n - sumd];return res;}U perm(const int n, const int r) {if (n < 0 or r < 0 or n < r) return 0;ensure(n);return _fac[n] * _fac_inv[n - r];}private:static std::vector<T> _fac;static std::vector<U> _fac_inv;};template <typename T, typename U>std::vector<T> factorial<T, U>::_fac{ 1 };template <typename T, typename U>std::vector<U> factorial<T, U>::_fac_inv{ 1 };} // namespace suisenusing suisen::bigint;mint solve(int N, std::vector<bigint>& A, bigint M) {suisen::factorial<mint> fact(10000000);std::vector<bigint> Mt(N + 1);Mt[N] = M;for (int i = N - 1; i >= 0; --i) {Mt[i] = Mt[i + 1] / A[i];}std::vector binom_table(N + 2, std::vector<mint>(N + 2));for (int i = 0; i <= N + 1; ++i) {binom_table[i][0] = 1;for (int j = 1; j <= i; ++j) {binom_table[i][j] = binom_table[i - 1][j - 1] + binom_table[i - 1][j];}}std::vector<mint> pd(N + 1);for (int x = 0; x <= N; ++x) {auto binom = [](bigint n, int r) -> mint {if (r < 0 or bigint(r) > n) return 0;mint n2 = (int) bigint::divmod(n, mint::mod()).second;mint num = 1, den = 1;for (int i = 0; i < r; ++i) {num *= n2 - i;den *= 1 + i;}return num / den;};pd[x] = binom(bigint(N) + (Mt[0] - bigint(x)), N);}const int z = 1 << std::bit_width<unsigned>(2 * N);const mint iz = mint(z).inv();for (int t = 1; t <= N; ++t) {const int At = A[t - 1];// x_i,...,x_n < Atconst int u = N - t;const int Rt = Mt[t] % bigint(At);std::vector<mint> dp(N + 1);std::vector<mint> a(N + 1);for (int i = 0; i <= N; ++i) {a[i] = (i & 1 ? -1 : 1) * binom_table[u + 1][i];}std::reverse(pd.begin(), pd.end());std::vector<mint> f = atcoder::convolution(a, pd);f.resize(N + 1);std::vector<mint> b(z);for (int x = 0; x <= N; ++x) {for (int i = 0; i <= N; ++i) {dp[x] += f[N - i] * fact.binom(Rt - x + i * At + u, u);}}pd.swap(dp);}return pd[0];}int main() {int N;std::cin >> N;--N;std::vector<bigint> A(N);for (auto& e : A) std::cin >> e;std::reverse(A.begin(), A.end());bigint M;std::cin >> M;std::cout << solve(N, A, M).val() << std::endl;}