/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
#define trav(a, x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9 + 7; // 998244353; // = (119<<23)+1
const int MX = 2e5 + 5;

template<class T>
bool ckmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}

template<class T>
bool ckmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template<typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template<typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template<class X, class Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> const &p) {
    return os << p.first << " " << p.second;
}

template<class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, Container const &x) {
    bool first = true;
    for (auto &y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}


#include <iostream>
#include <assert.h>


#include <string>
#include <stdexcept>

#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
        if(!(condition)) { \
            throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
        }
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif


template<typename T, typename = std::true_type>
struct IdentityHelper;

template<typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
    static T identity() {
        return 1;
    }
};

template<typename T>
T identity() {
    return IdentityHelper<T>::identity();
}


/**
* ax + by = result
*/
template<typename T>
T extendedGcd(T a, T b, T &x, T &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    T d = extendedGcd(b % a, a, y, x);
    x -= (b / a) * y;
    return d;
}

template<typename T>
class Zn {
public:
    Zn() : value(0) {
    }

    Zn(int64_t value) : value(value) {
        int x = static_cast<int>(value % mod());
        if (x < 0) {
            x += mod();
        }
        this->value = x;
    }

    template<typename U>
    static Zn valueOf(U value) {
        int x = static_cast<int>(value % mod());
        if (x < 0) {
            x += mod();
        }
        return Zn(x);
    }

    static Zn rawValueOf(int value) {
        SPCPPL_ASSERT(value >= 0 && value < mod());
        return Zn(value);
    }

    template<typename U>
    Zn &operator=(U rhs) {
        return *this = Zn::valueOf(rhs);
    }


    Zn &operator+=(const Zn &rhs) {
        value += rhs.value;
        if (value >= mod()) {
            value -= mod();
        }
        return *this;
    }

    template<typename U>
    Zn &operator+=(U rhs) {
        return *this += Zn::valueOf(rhs);
    }

    Zn &operator-=(const Zn &rhs) {
        value -= rhs.value;
        if (value < 0) {
            value += mod();
        }
        return *this;
    }

    template<typename U>
    Zn &operator-=(U rhs) {
        return *this -= Zn::valueOf(rhs);
    }

    Zn &operator*=(const Zn &rhs) {
        long long result = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        value = static_cast<int>(result % mod());
        return *this;
    }

    template<typename U>
    Zn &operator*=(U rhs) {
        return *this *= Zn::valueOf(rhs);
    }

    Zn operator-() const {
        if (value == 0) {
            return *this;
        } else {
            return Zn(mod() - value);
        }
    }

    Zn &operator/=(const Zn &rhs) {
        return *this *= rhs.inversed();
    }

    template<typename U>
    Zn &operator/=(U rhs) {
        return *this /= Zn::valueOf(rhs);
    }

    Zn inv() const {
        return inversed();
    }

    inline Zn inversed() const {
        SPCPPL_ASSERT(value != 0);

        int x, y;
        int gcd = extendedGcd(value, mod(), x, y);
        (void) gcd;
        SPCPPL_ASSERT(gcd == 1);

        if (x < 0) {
            x += mod();
        }
        return Zn(x);
    }

    template<typename U>
    friend std::ostream &operator<<(std::ostream &, const Zn<U> &zn);

    template<typename U>
    friend std::istream &operator>>(std::istream &, Zn<U> &zn);

    template<typename U>
    friend bool operator==(const Zn<U> &lhs, const Zn<U> &rhs);

    int intValue() const {
        return value;
    }

    operator int64_t() const {
        return value;
    }

    constexpr static int mod() {
        return T::value;
    }

private:
    int value;

    template<int N = T::value>
    static constexpr bool correct_or_runtime(int) {
        return N > 0 && N <= (1 << 30);
    }

    static constexpr bool correct_or_runtime(...) {
        return true;
    }

    static_assert(
            std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
            "T::value must be int"
    );
    static_assert(correct_or_runtime(0), "Mod has to be positive integer up to 1 << 30");
};

template<typename T>
bool operator==(const Zn<T> &lhs, const Zn<T> &rhs) {
    return lhs.value == rhs.value;
}

template<typename T, typename U>
bool operator==(const Zn<T> &lhs, U rhs) {
    return lhs == Zn<T>::valueOf(rhs);
}

template<typename T, typename U>
bool operator==(U lhs, const Zn<T> &rhs) {
    return rhs == lhs;
}

template<typename T>
bool operator!=(const Zn<T> &lhs, const Zn<T> &rhs) {
    return !(lhs == rhs);
}

template<typename T, typename U>
bool operator!=(const Zn<T> &lhs, U rhs) {
    return !(lhs == rhs);
}

template<typename T, typename U>
bool operator!=(U lhs, const Zn<T> &rhs) {
    return !(lhs == rhs);
}

template<typename T>
Zn<T> operator+(const Zn<T> &lhs, const Zn<T> &rhs) {
    Zn<T> copy = lhs;
    return copy += rhs;
}

template<typename T, typename U>
Zn<T> operator+(const Zn<T> &lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy += rhs;
}

template<typename T, typename U>
Zn<T> operator+(U lhs, const Zn<T> &rhs) {
    return rhs + lhs;
}

template<typename T>
Zn<T> operator-(const Zn<T> &lhs, const Zn<T> &rhs) {
    Zn<T> copy = lhs;
    return copy -= rhs;
}

template<typename T, typename U>
Zn<T> operator-(const Zn<T> &lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy -= rhs;
}

template<typename T, typename U>
Zn<T> operator-(U lhs, const Zn<T> &rhs) {
    return Zn<T>::valueOf(lhs) - rhs;
}

template<typename T>
Zn<T> operator*(const Zn<T> &lhs, const Zn<T> &rhs) {
    Zn<T> copy = lhs;
    return copy *= rhs;
}

template<typename T, typename U>
Zn<T> operator*(const Zn<T> &lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy *= rhs;
}

template<typename T, typename U>
Zn<T> operator*(U lhs, const Zn<T> &rhs) {
    return rhs * lhs;
}

template<typename T>
Zn<T> operator/(const Zn<T> &lhs, const Zn<T> &rhs) {
    Zn<T> copy = lhs;
    return copy /= rhs;
}

template<typename T, typename U>
Zn<T> operator/(const Zn<T> &lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy /= rhs;
}

template<typename T, typename U>
Zn<T> operator/(U lhs, const Zn<T> &rhs) {
    return Zn<T>::valueOf(lhs) / rhs;
}

template<typename T>
std::ostream &operator<<(std::ostream &stream, const Zn<T> &zn) {
    return stream << zn.value;
}

template<typename T>
std::istream &operator>>(std::istream &stream, Zn<T> &zn) {
    int64_t value;
    stream >> value;
    zn.value = static_cast<int>(value % T::value);
    return stream;
}

template<typename T>
struct IdentityHelper<Zn<T>> {
    static Zn<T> identity() {
        return Zn<T>::valueOf(1);
    }
};

template<int m>
using ZnConst = Zn<std::integral_constant<int, m>>;

using Zn7 = ZnConst<1000000007>;


#include <cstdlib>

#ifndef SPCPPL_IGNORE_ASSERTS

void assert_re(bool value) {
    if (!value) {
        std::exit(1);
    }
}

void assert_tl(bool value) {
    if (!value) {
        while (true) {
        }
    }
}

void assert_wa(bool value) {
    if (!value) {
        std::cout << "karamba";
        std::exit(0);
    }
}

#else
#define assert_re(x)
#define assert_tl(x)
#define assert_wa(x)
#endif


using namespace std;
namespace algebra {
    const int inf = 1e9;
    const int magic = 500; // threshold for sizes to run the naive algo

    namespace fft {
        const int maxn = 1 << 17;

        typedef double ftype;
        typedef complex<ftype> point;

        vector<point> w(maxn);
        vector<point> A(maxn), B(maxn);
        vector<point> C(maxn), D(maxn);
        const ftype pi = acos(-1);
        bool initiated = 0;

        void init(int n) {
            if (!initiated or n > w.size()) {
                w.resize(n);
                A.resize(n);
                B.resize(n);
                C.resize(n);
                D.resize(n);
                for (int i = 1; i < w.size(); i *= 2) {
                    for (int j = 0; j < i; j++) {
                        w[i + j] = polar(ftype(1), pi * j / i);
                    }
                }
                initiated = 1;
            }
        }

        template<typename T>
        void fft(T *in, point *out, int n, int k = 1) {
            if (n == 1) {
                *out = *in;
            } else {
                n /= 2;
                fft(in, out, n, 2 * k);
                fft(in + k, out + n, n, 2 * k);
                for (int i = 0; i < n; i++) {
                    auto t = out[i + n] * w[i + n];
                    out[i + n] = out[i] - t;
                    out[i] += t;
                }
            }
        }

        template<typename T>
        void mul_slow(vector<T> &a, const vector<T> &b) {
            if (not a.empty() or not b.empty()) {
                vector<T> res(a.size() + b.size() - 1);
                for (size_t i = 0; i < a.size(); i++) {
                    for (size_t j = 0; j < b.size(); j++) {
                        res[i + j] = res[i + j] + a[i] * b[j];
                    }
                }
                a = res;
            }
        }


        template<typename T>
        void mul(vector<T> &a, const vector<T> &b) {
            if (min(a.size(), b.size()) < magic) {
                mul_slow(a, b);
                return;
            }
            static const int shift = 15, mask = (1 << shift) - 1;
            size_t n = a.size() + b.size() - 1;
            while (__builtin_popcount(n) != 1) {
                n++;
            }
            a.resize(n);
            init(n);
            for (size_t i = 0; i < n; i++) {
                A[i] = point(a[i] & mask, a[i] >> shift);
                if (i < b.size()) {
                    B[i] = point(b[i] & mask, b[i] >> shift);
                } else {
                    B[i] = 0;
                }
            }
            fft(A.data(), C.data(), n);
            fft(B.data(), D.data(), n);
            for (size_t i = 0; i < n; i++) {
                point c0 = C[i] + conj(C[(n - i) % n]);
                point c1 = C[i] - conj(C[(n - i) % n]);
                point d0 = D[i] + conj(D[(n - i) % n]);
                point d1 = D[i] - conj(D[(n - i) % n]);
                A[i] = c0 * d0 - point(0, 1) * c1 * d1;
                B[i] = c0 * d1 + d0 * c1;
            }
            fft(A.data(), C.data(), n);
            fft(B.data(), D.data(), n);
            reverse(C.begin() + 1, C.begin() + n);
            reverse(D.begin() + 1, D.begin() + n);
            int t = 4 * n;
            for (size_t i = 0; i < n; i++) {
                int64_t A0 = llround(real(C[i]) / t);
                T A1 = llround(imag(D[i]) / t);
                T A2 = llround(imag(C[i]) / t);
                a[i] = A0 + (A1 << shift) + (A2 << 2 * shift);
            }
            return;
        }
    }

    template<typename T>
    T bpow(T x, size_t n) {
        return n ? n % 2 ? x * bpow(x, n - 1) : bpow(x * x, n / 2) : T(1);
    }

    template<typename T>
    T bpow(T x, size_t n, T m) {
        return n ? n % 2 ? x * bpow(x, n - 1, m) % m : bpow(x * x % m, n / 2, m) : T(1);
    }

    template<typename T>
    T gcd(const T &a, const T &b) {
        return b == T(0) ? a : gcd(b, a % b);
    }

    template<typename T>
    T nCr(T n, int r) { // runs in O(r)
        T res(1);
        for (int i = 0; i < r; i++) {
            res *= (n - T(i));
            res /= (i + 1);
        }
        return res;
    }

    template<typename T>
    struct poly {
        vector<T> a;

        void normalize() { // get rid of leading zeroes
            while (!a.empty() && a.back() == T(0)) {
                a.pop_back();
            }
        }

        poly() {}

        poly(T a0) : a{a0} { normalize(); }

        poly(vector<T> t) : a(t) { normalize(); }

        poly operator+=(const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for (size_t i = 0; i < t.a.size(); i++) {
                a[i] += t.a[i];
            }
            normalize();
            return *this;
        }

        poly operator-=(const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for (size_t i = 0; i < t.a.size(); i++) {
                a[i] -= t.a[i];
            }
            normalize();
            return *this;
        }

        poly operator+(const poly &t) const { return poly(*this) += t; }

        poly operator-(const poly &t) const { return poly(*this) -= t; }

        poly mod_xk(size_t k) const { // get same polynomial mod x^k
            k = min(k, a.size());
            return vector<T>(begin(a), begin(a) + k);
        }

        poly mul_xk(size_t k) const { // multiply by x^k
            poly res(*this);
            res.a.insert(begin(res.a), k, 0);
            return res;
        }

        poly div_xk(size_t k) const { // divide by x^k, dropping coefficients
            k = min(k, a.size());
            return vector<T>(begin(a) + k, end(a));
        }

        poly substr(size_t l, size_t r) const { // return mod_xk(r).div_xk(l)
            l = min(l, a.size());
            r = min(r, a.size());
            return vector<T>(begin(a) + l, begin(a) + r);
        }

        poly inv(size_t n) const { // get inverse series mod x^n
            assert(!is_zero());
            poly ans = a[0].inv();
            size_t a = 1;
            while (a < n) {
                poly C = (ans * mod_xk(2 * a)).substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);
        }

        poly operator*=(const poly &t) {
            fft::mul(a, t.a);
            normalize();
            return *this;
        }

        poly operator*(const poly &t) const { return poly(*this) *= t; }

        poly reverse(size_t n, bool rev = 0) const { // reverses and leaves only n terms
            poly res(*this);
            if (rev) { // If rev = 1 then tail goes to head
                res.a.resize(max(n, res.a.size()));
            }
            std::reverse(res.a.begin(), res.a.end());
            return res.mod_xk(n);
        }

        pair<poly, poly> divmod_slow(const poly &b) const { // when divisor or quotient is small
            vector<T> A(a);
            vector<T> res;
            while (A.size() >= b.a.size()) {
                res.push_back(A.back() / b.a.back());
                if (res.back() != T(0)) {
                    for (size_t i = 0; i < b.a.size(); i++) {
                        A[A.size() - i - 1] -= res.back() * b.a[b.a.size() - i - 1];
                    }
                }
                A.pop_back();
            }
            std::reverse(begin(res), end(res));
            return {res, A};
        }

        pair<poly, poly> divmod(const poly &b) const { // returns quotiend and remainder of a mod b
            if (deg() < b.deg()) {
                return {poly{0}, *this};
            }
            int d = deg() - b.deg();
            if (min(d, b.deg()) < magic) {
                return divmod_slow(b);
            }
            poly D = (reverse(d + 1) * b.reverse(d + 1).inv(d + 1)).mod_xk(d + 1).reverse(d + 1, 1);
            return {D, *this - D * b};
        }

        poly operator/(const poly &t) const { return divmod(t).first; }

        poly operator%(const poly &t) const { return divmod(t).second; }

        poly operator/=(const poly &t) { return *this = divmod(t).first; }

        poly operator%=(const poly &t) { return *this = divmod(t).second; }

        poly operator*=(const T &x) {
            for (auto &it: a) {
                it *= x;
            }
            normalize();
            return *this;
        }

        poly operator/=(const T &x) {
            for (auto &it: a) {
                it /= x;
            }
            normalize();
            return *this;
        }

        poly operator*(const T &x) const { return poly(*this) *= x; }

        poly operator/(const T &x) const { return poly(*this) /= x; }

        T eval(T x) const { // evaluates in single point x
            T res(0);
            for (int i = int(a.size()) - 1; i >= 0; i--) {
                res *= x;
                res += a[i];
            }
            return res;
        }

        T &lead() { // leading coefficient
            return a.back();
        }

        int deg() const { // degree
            return a.empty() ? -inf : a.size() - 1;
        }

        bool is_zero() const { // is polynomial zero
            return a.empty();
        }

        T operator[](int idx) const {
            return idx >= (int) a.size() || idx < 0 ? T(0) : a[idx];
        }

        T &coef(size_t idx) { // mutable reference at coefficient
            return a[idx];
        }

        bool operator==(const poly &t) const { return a == t.a; }

        bool operator!=(const poly &t) const { return a != t.a; }

        poly deriv() { // calculate derivative
            vector<T> res;
            for (int i = 1; i <= deg(); i++) {
                res.push_back(T(i) * a[i]);
            }
            return res;
        }

        poly integr() { // calculate integral with C = 0
            vector<T> res = {0};
            for (int i = 0; i <= deg(); i++) {
                res.push_back(a[i] / T(i + 1));
            }
            return res;
        }

        size_t leading_xk() const { // Let p(x) = x^k * t(x), return k
            if (is_zero()) {
                return inf;
            }
            int res = 0;
            while (a[res] == T(0)) {
                res++;
            }
            return res;
        }

        poly log(size_t n) { // calculate log p(x) mod x^n
            assert(a[0] == T(1));
            return (deriv().mod_xk(n) * inv(n)).integr().mod_xk(n);
        }

        poly exp(size_t n) { // calculate exp p(x) mod x^n
            if (is_zero()) {
                return T(1);
            }
            assert(a[0] == T(0));
            poly ans = T(1);
            size_t a = 1;
            while (a < n) {
                poly C = ans.log(2 * a).div_xk(a) - substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);

        }

        poly pow_slow(size_t k, size_t n) { // if k is small
            return k ? k % 2 ? (*this * pow_slow(k - 1, n)).mod_xk(n) : (*this * *this).mod_xk(n).pow_slow(k / 2, n)
                     : T(1);
        }

        poly pow(size_t k, size_t n) { // calculate p^k(n) mod x^n
            if (is_zero()) {
                return *this;
            }
            if (k < magic) {
                return pow_slow(k, n);
            }
            int i = leading_xk();
            T j = a[i];
            poly t = div_xk(i) / j;
            return bpow(j, k) * (t.log(n) * T(k)).exp(n).mul_xk(i * k).mod_xk(n);
        }

        poly mulx(T x) { // component-wise multiplication with x^k
            T cur = 1;
            poly res(*this);
            for (int i = 0; i <= deg(); i++) {
                res.coef(i) *= cur;
                cur *= x;
            }
            return res;
        }

        poly mulx_sq(T x) { // component-wise multiplication with x^{k^2}
            T cur = x;
            T total = 1;
            T xx = x * x;
            poly res(*this);
            for (int i = 0; i <= deg(); i++) {
                res.coef(i) *= total;
                total *= cur;
                cur *= xx;
            }
            return res;
        }

        vector<T> chirpz_even(T z, int n) { // P(1), P(z^2), P(z^4), ..., P(z^2(n-1))
            int m = deg();
            if (is_zero()) {
                return vector<T>(n);
            }
            vector<T> vv(m + n);
            T zi = z.inv();
            T zz = zi * zi;
            T cur = zi;
            T total = 1;
            for (int i = 0; i <= max(n - 1, m); i++) {
                if (i <= m) { vv[m - i] = total; }
                if (i < n) { vv[m + i] = total; }
                total *= cur;
                cur *= zz;
            }
            poly w = (mulx_sq(z) * vv).substr(m, m + n).mulx_sq(z);
            vector<T> res(n);
            for (int i = 0; i < n; i++) {
                res[i] = w[i];
            }
            return res;
        }

        vector<T> chirpz(T z, int n) { // P(1), P(z), P(z^2), ..., P(z^(n-1))
            auto even = chirpz_even(z, (n + 1) / 2);
            auto odd = mulx(z).chirpz_even(z, n / 2);
            vector<T> ans(n);
            for (int i = 0; i < n / 2; i++) {
                ans[2 * i] = even[i];
                ans[2 * i + 1] = odd[i];
            }
            if (n % 2 == 1) {
                ans[n - 1] = even.back();
            }
            return ans;
        }

        template<typename iter>
        vector<T> eval(vector<poly> &tree, int v, iter l, iter r) { // auxiliary evaluation function
            if (r - l == 1) {
                return {eval(*l)};
            } else {
                auto m = l + (r - l) / 2;
                auto A = (*this % tree[2 * v]).eval(tree, 2 * v, l, m);
                auto B = (*this % tree[2 * v + 1]).eval(tree, 2 * v + 1, m, r);
                A.insert(end(A), begin(B), end(B));
                return A;
            }
        }

        vector<T> eval(vector<T> x) { // evaluate polynomial in (x1, ..., xn)
            int n = x.size();
            if (is_zero()) {
                return vector<T>(n, T(0));
            }
            vector<poly> tree(4 * n);
            build(tree, 1, begin(x), end(x));
            return eval(tree, 1, begin(x), end(x));
        }

        template<typename iter>
        poly inter(vector<poly> &tree, int v, iter l, iter r, iter ly, iter ry) { // auxiliary interpolation function
            if (r - l == 1) {
                return {*ly / a[0]};
            } else {
                auto m = l + (r - l) / 2;
                auto my = ly + (ry - ly) / 2;
                auto A = (*this % tree[2 * v]).inter(tree, 2 * v, l, m, ly, my);
                auto B = (*this % tree[2 * v + 1]).inter(tree, 2 * v + 1, m, r, my, ry);
                return A * tree[2 * v + 1] + B * tree[2 * v];
            }
        }
    };

    template<typename T>
    poly<T> operator*(const T &a, const poly<T> &b) {
        return b * a;
    }

    template<typename T>
    poly<T> xk(int k) { // return x^k
        return poly<T>{1}.mul_xk(k);
    }

    template<typename T>
    T resultant(poly<T> a, poly<T> b) { // computes resultant of a and b
        if (b.is_zero()) {
            return 0;
        } else if (b.deg() == 0) {
            return bpow(b.lead(), a.deg());
        } else {
            int pw = a.deg();
            a %= b;
            pw -= a.deg();
            T mul = bpow(b.lead(), pw) * T((b.deg() & a.deg() & 1) ? -1 : 1);
            T ans = resultant(b, a);
            return ans * mul;
        }
    }

    template<typename iter>
    poly<typename iter::value_type> kmul(iter L, iter R) { // computes (x-a1)(x-a2)...(x-an) without building tree
        if (R - L == 1) {
            return vector<typename iter::value_type>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return kmul(L, M) * kmul(M, R);
        }
    }

    template<typename T, typename iter>
    poly<T> build(vector<poly<T>> &res, int v, iter L, iter R) { // builds evaluation tree for (x-a1)(x-a2)...(x-an)
        if (R - L == 1) {
            return res[v] = vector<T>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return res[v] = build(res, 2 * v, L, M) * build(res, 2 * v + 1, M, R);
        }
    }

    template<typename T>
    poly<T> build(const vector<T> roots) {
        if (roots.empty()) {
            return 1;
        }
        vector<poly<T>> tree(4 * roots.size());
        return build(tree, 1, begin(roots), end(roots));
    }

    template<typename T>
    poly<T> inter(vector<T> x, vector<T> y) { // interpolates minimum polynomial from (xi, yi) pairs
        int n = x.size();
        vector<poly<T>> tree(4 * n);
        return build(tree, 1, begin(x), end(x)).deriv().inter(tree, 1, begin(x), end(x), begin(y), end(y));
    }

    template<typename T>
    ostream &operator<<(ostream &os, const poly<T> P) {
        for (auto it: P.a) {
            os << it << ' ';
        }
        return os << endl;
    }
};

using namespace algebra;

//const int mod = 1e9 + 7;
//typedef modular<mod> base;
//typedef poly<base> polyn;

//using namespace algebra;

//signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    int n = 100000;
//    polyn a;
//    vector<base> x;
//    for(int i = 0; i <= n; i++) {
//        a.a.push_back(1 + rand() % 100);
//        x.push_back(1 + rand() % (2 * n));
//    }
//    sort(begin(x), end(x));
//    x.erase(unique(begin(x), end(x)), end(x));
//    auto b = a.eval(x);
//    cout << clock() / double(CLOCKS_PER_SEC) << endl;
//    auto c = inter(x, b);
//    polyn md = kmul(begin(x), end(x));
//    cout << clock() / double(CLOCKS_PER_SEC) << endl;
//    assert(c == a % md);
//    return 0;
//}





template<typename T>
T binpow(T base, long long power) {
    SPCPPL_ASSERT(power >= 0);
//    T result = identity<T>();
    T result = (T) 1;
    while (power > 0) {
        if (power & 1) {
            result *= base;
        }
        power >>= 1;
        base *= base;
    }
    return result;
}


using namespace std;
using namespace algebra;

class FKnapsackForAllSubsets {

    using Z = ZnConst<998244353>;

    poly<Z> merge(const poly<Z> &A, const poly<Z> &B, int m) {
        poly<Z> C = (A * B).mod_xk(m);
    }

    poly<Z> pow(const poly<Z> &P, int n, int m) {
        poly<Z> A = P, res(1);
        for (; n; n /= 2) {
            if (n % 2) {
                res = merge(res, A, m);
            }
            A = merge(A, A, m);
        }
        return move(res);
    }

public:
    void solve(std::istream &in, std::ostream &out) {
        int n, s;
        in >> n >> s;
        vi A(n);
        in >> A;
        vector<Z> dp(s + 1);
        dp[0] = binpow((Z) 2, n);
        trav(x, A) {
            ROF(i, x, s + 1) {
                dp[i] += dp[i - x] / 2;
            }
        }
        Z res = dp[s];
        out << res << '\n';
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    FKnapsackForAllSubsets solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 13440