#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#include <cstdint>
#include <vector>
#include <utility>
namespace OY {
#define cin OY::inputHelper<1 << 18, 20>::getInstance()
#define getchar() ({char c=cin.getChar_Checked();cin.next();c; })
#define cout OY::outputHelper<1 << 18>::getInstance()
#define putchar cout.putChar
#define endl '\n'
#define putlog(...) OY::printLog(", ", __VA_ARGS__)
template <uint64_t _BufferSize = 1 << 18, uint64_t _BlockSize = 20>
class inputHelper {
public:
    FILE *m_filePtr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    bool m_ok;
    void flush() {
        uint64_t a = m_end - m_cursor;
        if (a >= _BlockSize) return;
        memmove(m_buf, m_cursor, a);
        uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
        m_cursor = m_buf;
        if (a + b < _BufferSize) {
            m_end = m_buf + a + b;
            *m_end = EOF;
        }
    }
public:
    explicit inputHelper(const char *inputFileName) : m_ok(true) {
        if (!*inputFileName) m_filePtr = stdin;
        else m_filePtr = fopen(inputFileName, "rt");
        m_end = m_cursor = m_buf + _BufferSize;
    }
    ~inputHelper() { fclose(m_filePtr); }
    static inputHelper<_BufferSize, _BlockSize> &getInstance() {
        static inputHelper<_BufferSize, _BlockSize> s_obj("");
        return s_obj;
    }
    static constexpr bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
    static constexpr bool isEndline(char c) { return c == '\n' || c == EOF; }
    const char &getChar_Checked() {
        if (m_cursor < m_end) return *m_cursor;
        uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
        m_cursor = m_buf;
        if (b < _BufferSize) {
            m_end = m_buf + b;
            *m_end = EOF;
        }
        return *m_cursor;
    }
    const char &getChar_Unchecked() const { return *m_cursor; }
    void next() { ++m_cursor; }
    void setState(bool _ok) { m_ok = _ok; }
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked())) next();
        flush();
        if (getChar_Unchecked() == '-') {
            next();
            if (isdigit(getChar_Unchecked())) {
                ret = -(getChar_Unchecked() - '0');
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 - (getChar_Unchecked() - '0');
            }
            else m_ok = false;
        }
        else {
            if (isdigit(getChar_Unchecked())) {
                ret = getChar_Unchecked() - '0';
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
            }
            else m_ok = false;
        }
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        while (isBlank(getChar_Checked())) next();
        flush();
        if (isdigit(getChar_Unchecked())) {
            ret = getChar_Unchecked() - '0';
            while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
        }
        else m_ok = false;
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
    inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
        bool neg = false, integer = false, decimal = false;
        while (isBlank(getChar_Checked())) next();
        flush();
        if (getChar_Unchecked() == '-') {
            neg = true;
            next();
        }
        if (!isdigit(getChar_Unchecked()) && getChar_Unchecked() != '.') {
            m_ok = false;
            return *this;
        }
        if (isdigit(getChar_Unchecked())) {
            integer = true;
            ret = getChar_Unchecked() - '0';
            while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
        }
        if (getChar_Unchecked() == '.') {
            next();
            if (isdigit(getChar_Unchecked())) {
                if (!integer) ret = 0;
                decimal = true;
                _Tp unit = 0.1;
                ret += unit * (getChar_Unchecked() - '0');
                while (next(), isdigit(getChar_Unchecked())) {
                    unit *= 0.1;
                    ret += unit * (getChar_Unchecked() - '0');
                }
            }
        }
        if (!integer && !decimal) m_ok = false;
        else if (neg) ret = -ret;
        return *this;
    }
    inputHelper<_BufferSize, _BlockSize> &operator>>(char &ret) {
        while (isBlank(getChar_Checked())) next();
        ret = getChar_Checked();
        if (ret == EOF) m_ok = false;
        else next();
        return *this;
    }
    inputHelper<_BufferSize, _BlockSize> &operator>>(std::string &ret) {
        while (isBlank(getChar_Checked())) next();
        if (getChar_Checked() != EOF) {
            ret.clear();
            do {
                ret += getChar_Checked();
                next();
            } while (!isBlank(getChar_Checked()) && getChar_Unchecked() != EOF);
        }
        else m_ok = false;
        return *this;
    }
    explicit operator bool() { return m_ok; }
};
template <uint64_t _BufferSize = 1 << 20>
class outputHelper {
    FILE *m_filePtr = nullptr;
    char m_buf[_BufferSize], *m_end, *m_cursor;
    char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
    uint64_t m_floatReserve, m_floatRatio;
public:
    outputHelper(const char *outputFileName, int prec = 6) : m_end(m_buf + _BufferSize) {
        if (!*outputFileName) m_filePtr = stdout;
        else m_filePtr = fopen(outputFileName, "wt");
        m_cursor = m_buf;
        m_tempBufCursor = m_tempBuf;
        precision(prec);
    }
    static outputHelper<_BufferSize> &getInstance() {
        static outputHelper<_BufferSize> s_obj("");
        return s_obj;
    }
    ~outputHelper() {
        flush();
        fclose(m_filePtr);
    }
    void precision(int prec) {
        m_floatReserve = prec;
        m_floatRatio = pow(10, prec);
        m_tempBufDot = m_tempBuf + prec;
    }
    outputHelper<_BufferSize> &flush() {
        fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
        fflush(m_filePtr);
        m_cursor = m_buf;
        return *this;
    }
    void putChar(const char &c) {
        if (m_cursor == m_end) flush();
        *m_cursor++ = c;
    }
    void putS(const char *c) { while (*c) putChar(*c++); }
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);
        if (_ret >= 0) {
            do {
                *m_tempBufCursor++ = '0' + _ret % 10;
                _ret /= 10;
            } while (_ret);
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
        }
        else {
            putChar('-');
            do {
                *m_tempBufCursor++ = '0' - _ret % 10;
                _ret /= 10;
            } while (_ret);
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
        }
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        _Tp _ret = _Tp(ret);
        do {
            *m_tempBufCursor++ = '0' + _ret % 10;
            _ret /= 10;
        } while (_ret);
        do putChar(*--m_tempBufCursor);
        while (m_tempBufCursor > m_tempBuf);
        return *this;
    }
    template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
    outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
        if (ret < 0) {
            putChar('-');
            return *this << -ret;
        }
        _Tp _ret = ret * m_floatRatio;
        uint64_t integer = _ret;
        if (_ret - integer >= 0.4999999999) integer++;
        do {
            *m_tempBufCursor++ = '0' + integer % 10;
            integer /= 10;
        } while (integer);
        if (m_tempBufCursor > m_tempBufDot) {
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBufDot);
            putChar('.');
        }
        else {
            putS("0.");
            for (int i = m_tempBufDot - m_tempBufCursor; i--;) putChar('0');
        }
        do putChar(*--m_tempBufCursor);
        while (m_tempBufCursor > m_tempBuf);
        return *this;
    }
    outputHelper<_BufferSize> &operator<<(const char &ret) {
        putChar(ret);
        return *this;
    }
    outputHelper<_BufferSize> &operator<<(const std::string &ret) {
        putS(ret.data());
        return *this;
    }
};
template <uint64_t _BufferSize, uint64_t _BlockSize>
inputHelper<_BufferSize, _BlockSize> &getline(inputHelper<_BufferSize, _BlockSize> &ih, std::string &ret) {
    ret.clear();
    if (ih.getChar_Checked() == EOF) ih.setState(false);
    else {
        while (!inputHelper<_BufferSize, _BlockSize>::isEndline(ih.getChar_Checked())) {
            ret += ih.getChar_Unchecked();
            ih.next();
        }
        ih.next();
    }
    return ih;
}
template <typename D, typename T, typename... S>
void printLog(D delim, const T &x, S... rest) {
    cout << x;
    if (sizeof...(rest) > 0) {
        cout << delim;
        printLog(delim, rest...);
    }
}
}
using OY::getline;
namespace OY {
template <typename _ModType, _ModType _P>
struct Modular {
    static constexpr _ModType mod() { return _P; }
    static constexpr _ModType mod(uint64_t __a) { return __a % _P; }
    static constexpr _ModType plus(_ModType __a, _ModType __b) {
        if (__a += __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType minus(_ModType __a, _ModType __b) {
        if (__a += _P - __b; __a >= _P) __a -= _P;
        return __a;
    }
    static constexpr _ModType multiply(uint64_t __a, uint64_t __b) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return multiply_ld(__a, __b);
        else return multiply_64(__a, __b);
    }
    static constexpr _ModType multiply_64(uint64_t __a, uint64_t __b) { return mod(__a * __b); }
    static constexpr _ModType multiply_128(uint64_t __a, uint64_t __b) { return __uint128_t(__a) * __b % _P; }
    static constexpr _ModType multiply_ld(uint64_t __a, uint64_t __b) {
        if (std::__countl_zero(__a) + std::__countl_zero(__b) >= 64) return multiply_64(__a, __b);
        int64_t res = __a * __b - uint64_t(1.L / _P * __a * __b) * _P;
        if (res < 0) res += _P;
        else if (res >= _P) res -= _P;
        return res;
    }
    static constexpr _ModType pow(uint64_t __a, uint64_t __n) {
        if constexpr (std::is_same<_ModType, uint64_t>::value) return pow_ld(__a, __n);
        else return pow_64(__a, __n);
    }
    static constexpr _ModType pow_64(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_64(res, b);
            b = multiply_64(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_128(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_128(res, b);
            b = multiply_128(b, b);
            __n >>= 1;
        }
        return res;
    }
    static constexpr _ModType pow_ld(uint64_t __a, uint64_t __n) {
        _ModType res = 1, b = mod(__a);
        while (__n) {
            if (__n & 1) res = multiply_ld(res, b);
            b = multiply_ld(b, b);
            __n >>= 1;
        }
        return res;
    }
    template <typename _Tp>
    static constexpr _Tp divide(_Tp __a) { return __a / _P; }
    template <typename _Tp>
    static constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) {
        _Tp quo = __a / _P, rem = __a - quo * _P;
        return {quo, rem};
    }
};
template <uint32_t _P>
using Modular32 = Modular<uint32_t, _P>;
template <uint64_t _P>
using Modular64 = Modular<uint64_t, _P>;
}
namespace OY {
template <typename _ModType, _ModType _P, bool _IsPrime = false>
struct StaticModInt {
    using mint = StaticModInt<_ModType, _P, _IsPrime>;
    _ModType m_val;
    static constexpr _ModType get_primitive_root_prime() {
        _ModType tmp[64] = {};
        int cnt = 0;
        const _ModType phi = _P - 1;
        _ModType m = phi;
        for (_ModType i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                tmp[cnt++] = i;
                do m /= i;
                while (m % i == 0);
            }
        }
        if (m != 1) tmp[cnt++] = m;
        for (StaticModInt res = 2;; res += 1) {
            bool f = true;
            for (int i = 0; i < cnt && f; ++i) f &= res.pow(phi / tmp[i]) != 1;
            if (f) return _ModType(res);
        }
    }
    static_assert(_P > 1 && _P < 1ull << 63);
    constexpr StaticModInt() : m_val(0) {}
    template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value, bool>::type = true>
    constexpr StaticModInt(_Tp __val) : m_val(0) {
        int64_t x = int64_t(__val) % int64_t(mod());
        if (x < 0) x += mod();
        m_val = x;
    }
    template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value, bool>::type = true>
    constexpr StaticModInt(_Tp __val) : m_val(__val % mod()) {}
    static constexpr mint raw(_ModType __val) {
        mint res;
        res.m_val = __val;
        return res;
    }
    static constexpr _ModType mod() { return _P; }
    constexpr _ModType val() const { return m_val; }
    constexpr mint pow(uint64_t __n) const { return Modular<_ModType, _P>::pow(m_val, __n); }
    constexpr mint inv() const {
        if constexpr (_IsPrime) return inv_Fermat();
        else return inv_exgcd();
    }
    constexpr mint inv_exgcd() const {
        _ModType x = mod(), y = m_val, m0 = 0, m1 = 1;
        while (y) {
            _ModType z = x / y;
            x -= y * z;
            m0 -= m1 * z;
            std::swap(x, y);
            std::swap(m0, m1);
        }
        if (m0 >= mod()) m0 += mod() / x;
        return raw(m0);
    }
    constexpr mint inv_Fermat() const { return pow(mod() - 2); }
    constexpr mint &operator++() {
        if (++m_val == mod()) m_val = 0;
        return *this;
    }
    constexpr mint &operator--() {
        if (m_val == 0) m_val = mod();
        m_val--;
        return *this;
    }
    constexpr mint operator++(int) {
        mint old(*this);
        ++*this;
        return old;
    }
    constexpr mint operator--(int) {
        mint old(*this);
        --*this;
        return old;
    }
    constexpr mint &operator+=(const mint &__other) {
        m_val = Modular<_ModType, _P>::plus(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator-=(const mint &__other) {
        m_val = Modular<_ModType, _P>::minus(m_val, __other.m_val);
            return *this;
    }
    constexpr mint &operator*=(const mint &__other) {
        m_val = Modular<_ModType, _P>::multiply(m_val, __other.m_val);
        return *this;
    }
    constexpr mint &operator/=(const mint &__other) { return *this *= __other.inv(); }
    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
    constexpr bool operator==(const mint &__other) const { return m_val == __other.m_val; }
    constexpr bool operator!=(const mint &__other) const { return m_val != __other.m_val; }
    constexpr bool operator<(const mint &__other) const { return m_val < __other.m_val; }
    constexpr bool operator>(const mint &__other) const { return m_val > __other.m_val; }
    constexpr bool operator<=(const mint &__other) const { return m_val <= __other.m_val; }
    constexpr bool operator>=(const mint &__other) const { return m_val <= __other.m_val; }
    template <typename _Tp>
    constexpr explicit operator _Tp() const { return _Tp(m_val); }
    constexpr friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    constexpr friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    constexpr friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    constexpr friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    template <typename _Istream>
    friend _Istream &operator>>(_Istream &is, mint &self) { return is >> self.m_val; }
    template <typename _Ostream>
    friend _Ostream &operator<<(_Ostream &os, const mint &self) { return os << self.m_val; }
};
template <uint32_t _P, bool _IsPrime>
using StaticModInt32 = StaticModInt<uint32_t, _P, _IsPrime>;
template <uint64_t _P, bool _IsPrime>
using StaticModInt64 = StaticModInt<uint64_t, _P, _IsPrime>;
}
using mint = OY::StaticModInt32<897581057, true>;
using std::vector;
namespace ntt {
static constexpr int lg_mod = std::__countr_zero(mint::mod() - 1);
static mint omegas[1 << lg_mod];
size_t max_omegas_len = 1;
int lg_max_omegas_len = 0;
inline void get_rev(size_t len, int x) {
    static constexpr mint G = mint(mint::get_primitive_root_prime()).pow((mint::mod() - 1) >> lg_mod);
    if (len == 1 || max_omegas_len >= len) return;
	omegas[0] = 1;
    omegas[1ul << x] = G.pow(1ul << (lg_mod - 2 - x));
    for (int i = x; i > lg_max_omegas_len; i--) omegas[1ul << (i - 1)] = omegas[1ul << i] * omegas[1ul << i];
    for (size_t i = max_omegas_len | 1ul; i < len; i++) omegas[i] = omegas[i & (i - 1)] * omegas[i & ((~i) + 1)];
    max_omegas_len = len;
    lg_max_omegas_len = x + 1;
}
inline void NTT(mint* a, size_t n) {
    for (size_t l = n >> 1; l; l >>= 1) {
        mint *k = a;
        for (mint *g = omegas; k < a + n; k += (l << 1), ++g) for (mint *x = k; x < k + l; x++) {
            mint o = x[l] * *g;
            x[l] = *x - o;
            *x += o;
        }
    }
}
inline void INTT(mint* a, size_t n) {
    for (size_t l = 1; l < n; l <<= 1) {
        mint *k = a;
        for (mint *g = omegas; k < a + n; k += (l << 1), ++g) for (mint *x = k; x < k + l; x++) {
            mint o = x[l];
            x[l] = *g * (*x - o);
            *x += o;
        }
    }
    mint invn = mint(n).inv();
    for (size_t i = 0; i < n; i++) a[i] *= invn;
	std::reverse(a + 1, a + n);
}
static mint buf[1 << lg_mod];
}
using ntt::get_rev;
using ntt::NTT;
using ntt::INTT;
inline vector<mint> operator*(const vector<mint>& a, const vector<mint>& b) {
    using ntt::buf;
    if (a.empty() || b.empty()) return {};
    size_t anssiz = a.size() + b.size() - 1;
    vector<mint> c(anssiz);
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    std::fill_n(std::copy_n(a.begin(), a.size(), buf), len - a.size(), mint(0));
    std::fill_n(std::copy_n(b.begin(), b.size(), buf + len), len - b.size(), mint(0));
    NTT(buf, len);
    NTT(buf + len, len);
    for (size_t i = 0; i < len; i++) buf[i] *= buf[i + len];
    INTT(buf, len);
    std::copy_n(buf, anssiz, c.begin());
    return c;
}
inline vector<mint>& operator*=(vector<mint>& a, const vector<mint>& b) {
    using ntt::buf;
    if (a.empty() || b.empty()) {
        a.clear();
        return a;
    }
    size_t anssiz = a.size() + b.size() - 1;
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    a.resize(len);
    std::fill_n(std::copy_n(b.begin(), b.size(), buf), len - b.size(), mint(0));
    NTT(a.data(), len);
    NTT(buf, len);
    for (size_t i = 0; i < len; i++) a[i] *= buf[i];
    INTT(a.data(), len);
    a.resize(anssiz);
    return a;
}
inline vector<mint> operator+(const vector<mint>& a, const vector<mint>& b) {
    vector<mint> c(a);
    c.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) c[i] += b[i];
    return c;
}
inline vector<mint>& operator+=(vector<mint>& a, const vector<mint>& b) {
    a.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) a[i] += b[i];
    return a;
}
inline vector<mint> operator-(const vector<mint>& a, const vector<mint>& b) {
    vector<mint> c(a);
    c.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) c[i] -= b[i];
    return c;
}
inline vector<mint>& operator-=(vector<mint>& a, const vector<mint>& b) {
    a.resize(std::max(a.size(), b.size()));
    for (size_t i = 0, iend = b.size(); i < iend; i++) a[i] -= b[i];
    return a;
}
namespace fac_base {
static constexpr mint inv2 = mint(2).inv();
static vector<mint> fac, invfac, inv;
inline void prepare_fac(size_t n) {
    size_t lastlen = fac.size();
    fac.resize(n + 1);
    invfac.resize(n + 1);
    inv.resize(n + 1);
    if (!lastlen) fac[0] = 1;
    for (size_t i = std::max<size_t>(lastlen, 1ul); i <= n; i++) fac[i] = fac[i - 1] * i;
    invfac[n] = fac[n].inv();
    if (lastlen) {
        for (size_t i = n; i >= lastlen; i--) {
            invfac[i - 1] = invfac[i] * i;
            inv[i] = fac[i - 1] * invfac[i];
        }
    }
    else {
        for (size_t i = n; i; i--) {
            invfac[i - 1] = invfac[i] * i;
            inv[i] = fac[i - 1] * invfac[i];
        }
    }
}
}
using fac_base::prepare_fac;
inline vector<mint> inverse(const vector<mint>& a, size_t l) {
    static constexpr mint two(2);
    vector<mint> b{a[0].inv()}, c;
    int x = 1;
    for (size_t lim = 4; lim < (l << 2); lim <<= 1, x++) {
        c.resize(lim);
        std::copy_n(a.begin(), std::min<size_t>(lim >> 1, a.size()), c.begin());
        b.resize(lim);
        get_rev(lim, x);
        NTT(c.data(), lim);
        NTT(b.data(), lim);
        for (size_t i = 0; i < lim; i++) b[i] *= two - (b[i] * c[i]);
        INTT(b.data(), lim);
        b.resize(lim >> 1);
    }
    b.resize(l);
    return b;
}
inline vector<mint> inverse(const vector<mint>& a) { return inverse(a, a.size()); }
inline vector<mint> operator%(const vector<mint>& a, const vector<mint>& b) {
    size_t n = a.size(), m = b.size();
    if (n < m) return a;
    vector<mint> F(a), G(b);
    vector<mint> Q(G);
    std::reverse(F.begin(), F.end());
    std::reverse(Q.begin(), Q.end());
    Q.resize(n - m + 1);
    Q = inverse(Q) * F;
    Q.resize(n - m + 1);
    std::reverse(Q.begin(), Q.end());
    std::reverse(F.begin(), F.end());
    Q *= G;
    Q.resize(m - 1);
    Q = F - Q;
    Q.resize(m - 1);
    return Q;
}
inline vector<mint> operator/(const vector<mint>& a, const vector<mint>& b) {
    size_t n = a.size(), m = b.size();
    vector<mint> F(a), G(b);
    vector<mint> Q(G);
    std::reverse(F.begin(), F.end());
    std::reverse(Q.begin(), Q.end());
    Q.resize(n - m + 1);
    Q = inverse(Q) * F;
    Q.resize(n - m + 1);
    std::reverse(Q.begin(), Q.end());
    std::reverse(F.begin(), F.end());
    return Q;
}
inline std::pair<vector<mint>, vector<mint> > div(const vector<mint>& a, const vector<mint>& b) {
    size_t n = a.size(), m = b.size();
    if (n < m || (n == m && a < b)) return {{}, a};
    vector<mint> F(a), G(b);
    vector<mint> Q(G);
    std::reverse(F.begin(), F.end());
    std::reverse(Q.begin(), Q.end());
    Q.resize(n - m + 1);
    Q = inverse(Q) * F;
    Q.resize(n - m + 1);
    std::reverse(Q.begin(), Q.end());
    std::reverse(F.begin(), F.end());
    std::pair<vector<mint>, vector<mint> > ret(Q, {});
    Q *= G;
    Q.resize(m - 1);
    ret.second = F - Q;
    ret.second.resize(m - 1);
    return ret;
}
inline vector<mint> derivate(const vector<mint>& a) {
    vector<mint> ans(a.size() - 1);
    for (size_t i = 1; i < a.size(); i++) ans[i - 1] = a[i] * i;
    return ans;
}
inline vector<mint> integrate(const vector<mint>& a) {
    vector<mint> ans(a.size() + 1);
    prepare_fac(a.size());
    for (size_t i = 1; i < a.size(); i++) ans[i] = a[i - 1] * fac_base::inv[i];
    return ans;
}
inline vector<mint> log(const vector<mint>& a) {
    vector<mint> tmp(inverse(a));
    tmp *= derivate(a);
    tmp = integrate(tmp);
    return tmp;
}
inline vector<mint> exp(const vector<mint>& a) {
    const size_t n = a.size();
    vector<mint> ans{1}, tmp;
    ans.reserve(n << 2);
    for (size_t lim = 2; lim <= (n << 1); lim <<= 1) {
        ans.resize(lim);
        tmp.resize(lim);
        std::copy_n(ans.begin(), std::min(lim >> 1, a.size()), tmp.begin());
        tmp = log(tmp);
        tmp.resize(lim);
        for (size_t i = 0, iend = std::min<size_t>(lim, a.size()); i < iend; i++) tmp[i] = a[i] - tmp[i];
        for (size_t i = std::min<size_t>(lim, a.size()); i < lim; i++) tmp[i] = -tmp[i];
        tmp[0]++;
        ans *= tmp;
        ans.resize(lim);
    }
    ans.resize(n);
    return ans;
}
namespace cipolla {
static constexpr mint none(-1);
static constexpr unsigned long long mod = mint::mod();
mint legrende(unsigned long long a) { return mint(a).pow((mod - 1) >> 1); }
mint find_nsqr(unsigned long long n) {
    for (unsigned long long i = 0; i < mod; i++) if (legrende(i * i - n) == none) return mint(i);
    return none;
}
mint a, n;
class cp {
    mint _M_real, _M_imag;
public:
    inline cp(const mint& r = mint(), const mint& i = mint()) : _M_real(r), _M_imag(i) {}
    inline cp(const cp& o) : _M_real(o._M_real), _M_imag(o._M_imag) {}
    inline cp& operator=(const cp& o) = default;
    inline cp& operator=(const mint& o) {
        _M_real = o;
        _M_imag = 0;
        return *this;
    }
    inline ~cp() = default;
    inline cp operator+(const cp& o) const { return cp(_M_real + o._M_real, _M_imag + o._M_imag); }
    inline cp operator*(const cp& o) const { return cp(_M_real * o._M_real + _M_imag * o._M_imag * (a * a - n), _M_real * o._M_imag + _M_imag * o._M_real); }
    friend inline cp operator-(const cp& o) { return cp(-o._M_real, -o._M_imag); }
    inline cp operator-(const cp& o) const { return *this + -o; }
    inline cp& operator+=(const cp& o) { return *this = *this + o; }
    inline cp& operator*=(const cp& o) { return *this = *this * o; }
    inline cp& operator-=(const cp& o) { return *this = *this - o; }
    inline mint& real() { return _M_real; }
    inline mint& imag() { return _M_imag; }
    inline const mint& real() const { return _M_real; }
    inline const mint& imag() const { return _M_imag; }
    inline cp conj() const { return cp(_M_real, -_M_imag); }
};
inline cp qpow(const cp& bs, unsigned long long po) {
    cp ans(1, 0), base(bs);
    while (po) {
        if (po & 1) ans *= base;
        base *= base;
        po >>= 1;
    }
    return ans;
}
inline mint sqrt(const mint& nn) {
    n = nn;
    if (n == mint(0)) return mint(0);
    if (legrende(n.val()) != 1) return none;
    a = find_nsqr(n.val());
    mint tmp = qpow(cp(a, 1), (mod + 1) >> 1).real();
    return tmp.val() < (-tmp).val() ? tmp : -tmp;
}
}
namespace sqr {
inline vector<mint> sqr(const vector<mint>& a) {
    using ntt::buf;
    size_t anssiz = a.size() * 2 - 1;
    vector<mint> c(anssiz);
    size_t len = 1;
    int x = -1;
    while (len < anssiz) len <<= 1, x++;
    get_rev(len, x);
    std::fill_n(std::copy_n(a.begin(), a.size(), buf), len - a.size(), mint(0));
    NTT(buf, len);
    for (size_t i = 0; i < len; i++) buf[i] *= buf[i];
    INTT(buf, len);
    std::copy_n(buf, anssiz, c.begin());
    return c;
}
}
vector<mint> sqrt(const vector<mint>& arr) {
    using cipolla::none;
    using fac_base::inv2;
    mint sqrt_of_first = cipolla::sqrt(arr[0]);
    static constexpr mint one(1);
    if (sqrt_of_first == none && arr[0] != one) return vector<mint>();
    vector<mint> ans{sqrt_of_first};
    const size_t n = arr.size();
    for (size_t lim = 2; lim < (n << 2); lim <<= 1) {
        ans = (sqr::sqr(ans) + arr) * inverse(ans);
        ans.resize(lim);
        for (mint& v : ans) v *= inv2;
    }
    ans.resize(arr.size());
    return ans;
}
namespace sin_cos {
static constexpr mint img = ((mint::mod() & 3) == 1) ? ((mint::mod() - 1) >> 2) : (mint::mod() - 1);
static constexpr mint inv2img = (img * 2).inv();
}
vector<mint> sin(const vector<mint>& arr) {
    vector<mint> tmp(arr);
    for (mint& v : tmp) v *= sin_cos::img;
    tmp = exp(tmp);
    vector<mint> ans(inverse(tmp));
    for (size_t i = 0, iend = arr.size(); i < iend; i++) ans[i] = (tmp[i] - ans[i]) * sin_cos::inv2img;
    return ans;
}
vector<mint> cos(const vector<mint>& arr) {
    using fac_base::inv2;
    vector<mint> tmp(arr);
    for (mint& v : tmp) v *= sin_cos::img;
    tmp = exp(tmp);
    vector<mint> ans(inverse(tmp));
    for (size_t i = 0, iend = arr.size(); i < iend; i++) ans[i] = (ans[i] + tmp[i]) * inv2;
    return ans;
}
vector<mint> asin(const vector<mint>& arr) {
    vector<mint> tmp(sqr::sqr(arr));
    for (mint& v : tmp) v = -v;
    tmp[0]++;
    return integrate(derivate(arr) * inverse(sqrt(tmp)));
}
vector<mint> atan(const vector<mint>& arr) {
    vector<mint> tmp(sqr::sqr(arr));
    tmp[0]++;
    return integrate(derivate(arr) * inverse(tmp));
}
vector<mint> pow(const vector<mint>& arr, size_t power) {
    auto it = std::find_if(arr.begin(), arr.end(), [=](const mint& v) { return v.val() != 0; });
    if (!power) {
        vector<mint> ans(arr.size(), mint(0));
        ans[0] = 1;
        return ans;
    }
    if ((it - arr.begin()) * power >= arr.size()) return vector<mint>(arr.size(), mint(0));
    vector<mint> ans(it, arr.end());
    mint tmp = it->inv();
    for (mint& v : ans) v *= tmp;
    ans = log(ans);
    for (mint& v : ans) v *= power;
    ans = exp(ans);
    tmp = it->pow(power);
    for (mint& v : ans) v *= tmp;
    ans.insert(ans.begin(), std::min<size_t>((it - arr.begin()) * power, arr.size()), mint(0));
    return ans;
}
vector<mint> pow(const vector<mint>& arr, size_t power, size_t __power, size_t __flg_power) {
    auto it = std::find_if(arr.begin(), arr.end(), [=](const mint& v) { return v.val() != 0; });
    if ((it - arr.begin()) * __flg_power >= arr.size() || it == arr.end()) return vector<mint>(arr.size(), mint(0));
    vector<mint> ans(it, arr.end());
    mint tmp = it->inv();
    for (mint& v : ans) v *= tmp;
    ans = log(ans);
    for (mint& v : ans) v *= power;
    ans = exp(ans);
    tmp = it->pow(__power);
    for (mint& v : ans) v *= tmp;
    ans.insert(ans.begin(), std::min<size_t>((it - arr.begin()) * power, arr.size()), mint(0));
    return ans;
}
namespace eval_base {
struct SegTree {
    size_t l, r;
    vector<mint> d, dr;
    SegTree *left, *right;
    inline void pushup_d() { d = right->dr * left->d + left->dr * right->d; }
    inline void pushup_dr() { dr = left->dr * right->dr; }
    inline void pushup() {
        pushup_d();
        pushup_dr();
    }
    void build_eval(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - arr[l];
            dr[1] = 1;
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_eval(arr);
        right->build_eval(arr);
        pushup();
    }
    void build_ffp(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - l;
            dr[1] = 1;
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_ffp(arr);
        right->build_ffp(arr);
        pushup();
    }
    void build_poly(const vector<mint>& arr) {
        if (l == r) {
            dr.resize(2);
            dr[0] = mint::mod() - l;
            dr[1] = 1;
            return;
        }
        left->build_poly(arr);
        right->build_poly(arr);
        pushup_dr();
    }
    void build_inter(const vector<mint>& arr) {
        if (l == r) {
            d.resize(1);
            d[0] = arr[l];
            return;
        }
        left->build_inter(arr);
        right->build_inter(arr);
        pushup_d();
    }
    void init_tree() {
        if (l == r) return;
        size_t mid = l + ((r - l) >> 1);
        left = new SegTree(l, mid);
        right = new SegTree(mid + 1, r);
        left->init_tree();
        right->init_tree();
    }
    SegTree(size_t il = 0, size_t ir = 0,
        const vector<mint>& d_ = vector<mint>(),
        const vector<mint>& dr_ = vector<mint>(),
        SegTree *ls = nullptr, SegTree *rs = nullptr)
        : l(il), r(ir), d(d_), dr(dr_), left(ls), right(rs) {}
};
SegTree *root;
vector<mint> ans;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->l == cur->r) {
        ans[cur->l] = arr[0];
        return;
    }
    eval_base::cdq(cur->left, arr % cur->left->dr);
    eval_base::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> eval(const vector<mint>& arr, const vector<mint>& point_x) {
    const size_t m = point_x.size();
    ans.resize(m);
    root = new SegTree(0, m);
    root->init_tree();
    root->build_eval(point_x);
    eval_base::cdq(root, arr);
    return ans;
}
}
using eval_base::eval;
namespace interpolation {
using eval_base::root;
using eval_base::SegTree;
using eval_base::ans;
vector<mint> tmparr;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->r - cur->l < 256) {
        for (size_t i = cur->l; i <= cur->r; i++) {
            mint tmp(0);
            const mint x(tmparr[i]);
            for (size_t j = arr.size() - 1; ~j; j--) tmp = tmp * x + arr[j];
            ans[i] = tmp;
        }
        return;
    }
    interpolation::cdq(cur->left, arr % cur->left->dr);
    interpolation::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> interpolate(const vector<mint>& point_x, const vector<mint>& point_y) {
    const size_t n = point_x.size();
    ans.resize(n);
    tmparr = point_x;
    root = new SegTree(0, n - 1);
    root->init_tree();
    root->build_eval(point_x);
    interpolation::cdq(root, derivate(root->dr));
    for (size_t i = 0; i < n; i++) ans[i] = point_y[i] / ans[i];
    root->build_inter(ans);
    ans = root->d;
    delete root;
    return ans;
}
}
using interpolation::interpolate;
namespace ffp {
using eval_base::root;
using eval_base::SegTree;
using eval_base::ans;
void cdq(SegTree *cur, const vector<mint>& arr) {
    if (cur->l == cur->r) {
        ans[cur->l] = arr[0];
        return;
    }
    ffp::cdq(cur->left, arr % cur->left->dr);
    ffp::cdq(cur->right, arr % cur->right->dr);
}
vector<mint> poly_to_ffp(const vector<mint>& arr) {
    using fac_base::invfac;
    const size_t n = arr.size();
    prepare_fac(n);
    ans.resize(n);
    vector<mint> tmp(n);
    root = new SegTree(0, n - 1);
    root->init_tree();
    root->build_poly(arr);
    ffp::cdq(root, arr);
    for (size_t i = 0; i < n; i++) {
        tmp[i] = i & 1 ? -invfac[i] : invfac[i];
        ans[i] *= invfac[i];
    }
    return ans * tmp;
}
vector<mint> ffp_to_poly(const vector<mint>& arr) {
    using fac_base::invfac;
    const size_t n = arr.size();
    prepare_fac(n);
    vector<mint> tmp = arr * invfac;
    tmp.resize(n + 1);
    for (size_t i = 0; i <= n; i++) {
        tmp[i] *= invfac[n - i];
        if ((n - i) & 1) tmp[i] = -tmp[i];
    }
    root = new SegTree(0, n);
    root->init_tree();
    root->build_ffp(tmp);
    tmp = root->d;
    delete root;
    return tmp;
}
}
using ffp::poly_to_ffp;
using ffp::ffp_to_poly;
vector<mint> shrink(const vector<mint>& arr) {
    vector<mint> a(arr);
    while (!a.empty() && a.back().val() == 0) a.pop_back();
    return a;
}
struct matrix {
    vector<mint> mat[2][2];
    matrix() = default;
    matrix(const vector<mint>& a00, const vector<mint>& a01,
           const vector<mint>& a10, const vector<mint>& a11)
        : mat({{a00, a01}, {a10, a11}}) {}
    matrix(const matrix&) = default;
    // TODO use 12E instead of now 48E
    inline matrix operator*(const matrix& o) const {
        return matrix{
            shrink(mat[0][0] * o.mat[0][0] + mat[0][1] * o.mat[1][0]),
            shrink(mat[0][0] * o.mat[0][1] + mat[0][1] * o.mat[1][1]),
            shrink(mat[1][0] * o.mat[0][0] + mat[1][1] * o.mat[1][0]),
            shrink(mat[1][0] * o.mat[0][1] + mat[1][1] * o.mat[1][1])
        };
    }
#if 0
    // 12E
    inline matrix& operator*=(const matrix& o) {
        size_t anssiz = std::max({
            mat[0][0].size() + o.mat[0][0].size(), mat[0][1].size() + o.mat[1][0].size(),
            mat[0][0].size() + o.mat[0][1].size(), mat[0][1].size() + o.mat[1][1].size(),
            mat[1][0].size() + o.mat[0][0].size(), mat[1][1].size() + o.mat[1][0].size(),
            mat[1][0].size() + o.mat[0][1].size(), mat[1][1].size() + o.mat[1][1].size()
        }) - 1;
        unsigned len = 1;
        while (len < anssiz) len <<= 1;
        int x = (int)log2(len);
        matrix cpy(o), ret{};
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
            NTT(mat[i][j].data(), x);
            NTT(cpy.mat[i][j].data(), x);
        }
        for (int i = 0; i < 2; i++) for (int k = 0; k < 2; k++) for (int j = 0; j < 2; j++) for (unsigned l = 0; l < len; l++) ret.mat[i][j][l] += mat[i][k][l] * cpy.mat[k][j][l];
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
            INTT(ret.mat[i][j].data(), x);
            mat[i][j] = shrink(ret.mat[i][j]);
        }
        return *this;
    }
#endif
    // TODO use 18E instead of now 24E
    inline std::pair<vector<mint>, vector<mint> > operator*(const std::pair<vector<mint>, vector<mint> >& o) const {
        return std::make_pair(
            shrink(mat[0][0] * o.first + mat[0][1] * o.second),
            shrink(mat[1][0] * o.first + mat[1][1] * o.second)
        );
    }
};
vector<mint> gcd(std::pair<vector<mint>, vector<mint> >& p) {
    auto [quo, rem] = div(p.first, p.second);
    p.first = p.second;
    p.second = rem;
    return quo;
}
vector<mint> operator<<(const vector<mint>& arr, size_t len) {
    vector<mint> ret(arr);
    ret.insert(ret.begin(), len, mint(0));
    return ret;
}
vector<mint> operator>>(const vector<mint>& arr, size_t len) {
	if (len >= arr.size()) return vector<mint>{};
	return vector<mint>(arr.begin() + len, arr.end());
}
inline matrix hgcd(const std::pair<vector<mint>, vector<mint> >& P) {
    size_t m = P.first.size() >> 1;
    if (P.second.size() <= m) return matrix{{1}, {}, {}, {1}};
    matrix R = hgcd(std::make_pair(P.first >> m, P.second >> m));
    std::pair<vector<mint>, vector<mint> > nP = R * P;
    if (nP.second.size() <= m) return R;
    vector<mint> Q(gcd(nP));
    matrix MQ({}, {1}, {1}, vector<mint>(Q.size(), mint()) - Q);
    if (nP.second.size() <= m) return MQ * R;
    size_t k = m * 2 - nP.first.size() + 1;
    return hgcd(std::make_pair(nP.first >> k, nP.second >> k)) * MQ * R;
}
inline matrix cogcd(const std::pair<vector<mint>, vector<mint> > &P) {
    matrix M = hgcd(P);
    std::pair<vector<mint>, vector<mint> > nP = M * P;
    if (nP.second.empty()) return M;
    vector<mint> Q(gcd(nP));
    matrix MQ({}, {1}, {1}, vector<mint>(Q.size(), mint()) - Q);
    if (nP.second.empty()) return MQ * M;
    return cogcd(nP) * MQ * M;
}
inline vector<mint> exgcd(std::pair<vector<mint>, vector<mint> > P, std::pair<vector<mint>, vector<mint> > &res) {
    matrix M;
    if (P.first.size() > P.second.size()) M = cogcd(P);
    else {
        vector<mint> Q(gcd(P));
        M = cogcd(P) * matrix({}, {1}, {1}, vector<mint>(Q.size(), mint()) - Q);
    }
    res.first = M.mat[0][0], res.second = M.mat[0][1];
    return shrink(P.first * res.first + P.second * res.second);
}
namespace bigint {
void flatten(vector<mint>& arr) {
    mint inc(0);
    for (size_t i = 0; i < arr.size(); i++) {
        arr[i] += inc;
        inc = arr[i].val() / 10;
        arr[i] = arr[i].val() % 10;
    }
    if (inc.val()) {
        while (inc.val() >= 10) {
            arr.push_back(inc.val() % 10);
            inc = inc.val() / 10;
        }
        arr.push_back(inc.val());
    }
}
}
vector<mint> mul(const vector<mint>& a, const vector<mint>& b) {
    vector<mint> tmp(a * b);
    bigint::flatten(tmp);
    return tmp;
}
namespace bigint {
bool less(const vector<mint> &a, const vector<mint> &b) {
    if (a.size() ^ b.size()) return a.size() < b.size();
    for (size_t i = a.size() - 1; ~i; i--) if (a[i] != b[i]) return a[i].val() < b[i].val();
    return false;
}
void flatten_add(vector<mint>& arr) {
    int inc(0);
    for (size_t i = 0; i < arr.size(); i++) {
        arr[i] += inc;
        inc = arr[i].val() >= 10;
        if (inc) arr[i] -= 10;
    }
    if (inc) arr.push_back(1);
}
void flatten_sub(vector<mint> &arr) {
    int carry = 0;
    static_assert(mint::mod() >= 100, "mint::mod() < 100");
    for (size_t i = 0; i < arr.size(); i++) {
        arr[i] -= carry;
        carry = arr[i].val() >= (mint::mod() - 100);
        if (carry) arr[i] += 10;
    }
    while (!arr.empty() && !arr.back().val()) arr.pop_back();
}
vector<mint> lsh(const vector<mint>& arr, size_t len) {
    vector<mint> ret(arr);
    ret.insert(ret.begin(), len, mint(0));
    return ret;
}
vector<mint> rsh(const vector<mint>& arr, size_t len) {
	if (len >= arr.size()) return vector<mint>{};
	return vector<mint>(arr.begin() + len, arr.end());
}
vector<mint> div_inv(const vector<mint>& arr) {
    size_t da = arr.size();
    size_t da0 = (da >> 1) + 1;
    if (da == 1) {
        vector<mint> tmp{100 / arr[0].val()};
        flatten(tmp);
        return tmp;
    }
    else if (da == 2) {
        vector<mint> tmp{10000 / (arr[1].val() * 10 + arr[0].val())};
        flatten(tmp);
        return tmp;
    }
    else {
        vector<mint> tmp(div_inv(rsh(arr, da - da0)));
        tmp = lsh(tmp, da - da0);
        vector<mint> tem{2};
        tem = lsh(tem, da << 1);
        tem -= mul(arr, tmp);
        flatten_sub(tem);
        return rsh(mul(tmp, tem), da << 1);
    }
}
}
namespace bigint {
vector<mint> div_inv_accurate(const vector<mint>& b) {
    vector<vector<mint> > t(7);
    t[0] = b;
    for (int i = 1; i ^ 7; ++i) {
        t[i] = t[i - 1] + t[i - 1];
        flatten_add(t[i]);
    }
    size_t n = b.size();
    size_t err = 0;
    auto res = div_inv(b), diff = lsh(vector<mint>{1}, n << 1) - mul(b, res);
    flatten_sub(diff);
    for (int i = 6; i >= 0; --i) if (!less(diff, t[i])) {
        diff -= t[i];
        flatten_sub(diff);
        err |= 1u << i;
    }
    res[0] += err;
    flatten(res);
    return res;
}
vector<mint> div(const vector<mint>& a, const vector<mint>& b) {
    int m = a.size(), n = b.size();
    if (m < n || (m == n && a < b)) return {mint(0)};
    vector<mint> rhs_p(b);
    int offset;
    if (m <= n << 1) offset = n << 1;
    else {
        offset = m + n;
        rhs_p.insert(rhs_p.begin(), m - n, mint(0));
    }
    auto res = rsh(mul(a, div_inv_accurate(rhs_p)), offset);
    auto ret = a - mul(res, b);
    flatten_sub(ret);
    if (less(ret, b)) ret = res;
    else {
        ret = res;
        ret[0]++;
        flatten_add(ret);
    }
    return ret;
}
}
int main() {
    vector<mint> a, b, c;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) a.push_back(ch & 15), ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) b.push_back(ch & 15), ch = getchar();
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    c = a + b;
    bigint::flatten_add(c);
    while (!c.empty() && c.back().val() == 0) c.pop_back();
    if (c.empty()) cout << '0';
    for (size_t i = c.size() - 1; ~i; i--) cout << c[i];
    cout << '\n';
    if (bigint::less(a, b)) {
        cout << '-';
        c = b - a;
    }
    else c = a - b;
    bigint::flatten_sub(c);
    while (!c.empty() && c.back().val() == 0) c.pop_back();
    if (c.empty()) cout << '0';
    for (size_t i = c.size() - 1; ~i; i--) cout << c[i];
    cout << '\n';
    c = mul(a, b);
    while (!c.empty() && c.back().val() == 0) c.pop_back();
    if (c.empty()) cout << '0';
    for (size_t i = c.size() - 1; ~i; i--) cout << c[i];
    cout << '\n';
    c = bigint::div(a, b);
    while (!c.empty() && c.back().val() == 0) c.pop_back();
    if (c.empty()) cout << '0';
    for (size_t i = c.size() - 1; ~i; i--) cout << c[i];
    cout << '\n';
    if (c.empty() || (c.size() == 1 && c[0] == 0)) {
        for (size_t i = a.size() - 1; ~i; i--) cout << a[i];
        cout << '\n';
        return 0;
    }
    c = a - mul(c, b);
    bigint::flatten_sub(c);
    while (!c.empty() && c.back().val() == 0) c.pop_back();
    if (c.empty()) cout << '0';
    for (size_t i = c.size() - 1; ~i; i--) cout << c[i];
    cout << '\n';
}