// N^3

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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 suisen

namespace 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^24
        static constexpr long long MOD2 = 167772161;  // 2^25
        static constexpr long long MOD3 = 469762049;  // 2^26
        static 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^24
        static constexpr long long MOD2 = 167772161;  // 2^25
        static constexpr long long MOD3 = 469762049;  // 2^26
        static 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 suisen

namespace 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_INT

            operator __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 suisen

namespace 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_INT

        operator __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 suisen

using 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<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);
    }

    std::vector<int> fac(5000000), ifac(5000000);
    for (int i = 0; i < 5000000; ++i) {
        fac[i] = fact.fac(i).val();
        ifac[i] = fact.fac_inv(i).val();
    }

    for (int t = 1; t <= N; ++t) {
        const int At = A[t - 1];

        // x_i,...,x_n < At
        const int u = N - t;
        const int Rt = Mt[t] % bigint(At);

        std::vector<mint> a(N + 1);
        for (int i = 0; i <= N; ++i) {
            a[i] = (i & 1 ? -1 : 1) * fact.binom(u + 1, i);
        }
        std::reverse(pd.begin(), pd.end());

        std::vector<mint> f = atcoder::convolution(a, pd);
        f.resize(N + 1);
        std::reverse(f.begin(), f.end());

        std::vector<__int128_t> dp(N + 1);

        for (int i = 0; i <= N; ++i) {
            const int T = At * i + Rt;
            const int maxk = std::min(N, T);
            const int fi = f[i].val();

            for (int k = 0; k <= maxk; ++k) {
                dp[k] += __int128_t((long long) (fac[T + u - k]) * ifac[T - k]) * fi;
            }
        }
        for (int k = 0; k <= N; ++k) {
            pd[k] = mint(dp[k] % mint::mod()) * ifac[u];
        }
    }

    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;
}