#include using namespace std; #define rep(i, n) for (decltype(n) i = 0; i < (n); ++i) #define rep3(i, s, n) for (decltype(n) i = (s); i < (n); ++i) #define repR(i, n) for (decltype(n) i = (n)-1; i >= 0; --i) #define rep3R(i, s, n) for (decltype(n) i = (n)-1; i >= (s); --i) #define repit(it, c) for (auto it = (c).begin(); it != (c).end(); ++it) #define all(x) ::std::begin(x), ::std::end(x) using ll = long long; template inline bool chmax(T ¤t, const U &test) { if (current < test) { current = test; return true; } return false; } template inline bool chmin(T ¤t, const U &test) { if (current > test) { current = test; return true; } return false; } using ll = long long; ll INF = 2 * 1e9; template T pow_mod(T n, T p, T mod) { T ret = 1; while (p > 0) { if (p & 1) { ret = ret * n % mod; } n = n * n % mod; p >>= 1; } return ret; } template T ext_gcd(T a, T b, T &x, T &y) { if (b == 0) { x = 1, y = 0; return a; } T d = ext_gcd(b, a % b, y, x); y -= a / b * x; return d; } template T inv_mod(T n, T mod) { T x(0), y(0); ext_gcd(n, mod, x, y); return (x % mod + mod) % mod; } template // Fast Modulo Transform class FMT { public: ll get_mod() const { return mod; } ll get_primitive_root() const { return primitive_root; } FMT() {} vector fmt(vector a, bool inverse = false) { ll n = a.size(); assert((n ^ (n & -n)) == 0); // power of 2 int h = 0; while ((1 << h) < n) { h++; } assert((1 << h) == n); // n == 2^h // bit reversal for (int i = 0; i < n; i++) { int i_rev = 0; for (int bit = 0; bit < h; bit++) { i_rev |= ((i >> bit) & 1) << (h - 1 - bit); } if (i < i_rev) swap(a[i], a[i_rev]); } // 1 の n = 2^e 乗根 ll w = pow_mod(primitive_root, (mod - 1) / n, mod); assert(pow_mod(w, n, mod) == 1); if (inverse) { w = inv_mod(w, mod); } // butterfly operation for (int b = 1; b < n; b *= 2) { // log_2(b) + 1 段 // ブロックサイズ = 2 * b ll base = pow_mod(w, n / (2 * b), mod); ll z = 1; for (int j = 0; j < b; j++) { //ブロック内 j 個目 for (int k = 0; k < n; k += 2 * b) { // k を先頭とするブロック ll s = a[j + k]; ll t = a[j + k + b] * z % mod; a[j + k] = (s + t) % mod; a[j + k + b] = (s - t + mod) % mod; } z = z * base % mod; } } if (inverse) { for (int i = 0; i < n; i++) { a[i] = a[i] * inv_mod(n, mod) % mod; } } return a; } vector ifmt(vector a) { return fmt(a, true); } vector convolve(vector a, vector b) { ll sz = a.size() + b.size() - 1; ll n = 1; while (n < sz) { n <<= 1; } a.resize(n); b.resize(n); vector A = fmt(a); vector B = fmt(b); for (int i = 0; i < n; i++) { A[i] = A[i] * B[i] % mod; } A = ifmt(A); a.resize(sz); for (int i = 0; i < sz; i++) { a[i] = A[i]; } return a; } }; FMT<998244353, 3> fmt; const ll mod = 998244353; // 分割統治 FFT ってこうで合ってますか? // a: 色 A の配列, 半開区間 [l, r), n: Fourier 空間での配列の長さ vector rec_convolve(vector &a, int l, int r, int n) { if (r - l == 1) { vector ret(n, 0); ret[0] = (a[l] - 1 + mod) % mod; // 色1 以外の場合の数 ret[1] = 1; // 色1 の場合の数 return ret; } int sz = r - l + 1; // x^0 から x^sz-1 までの sz 種類の冪 ll nn = 1; while (nn < sz) { nn <<= 1; } int mid = (l + r) / 2; vector ret(n, 0); vector v1 = rec_convolve(a, l, mid, nn); vector v2 = rec_convolve(a, mid, r, nn); ret = fmt.convolve(v1, v2); return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); constexpr char endl = '\n'; /////////////////////////// // input ll n, q; cin >> n >> q; vector a(n), b(q); for (auto &e : a) { cin >> e; e %= mod; } for (auto &e : b) { cin >> e; } // solve // 形式的冪級数で答えを書くと // [x^{B_q}] \prod_{i=1}^N ((A_i - 1) + 1 * x) FMT<998244353, 3> fmt; ll m = 1; while (m < n + 1) { m <<= 1; } vector v = rec_convolve(a, 0, n, m); // output rep(i, q) { cout << v[b[i]] << endl; } }