#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define per(i, n) for (int i = (n)-1; i >= 0; i--) #define rep2(i, l, r) for (int i = (l); i < (r); i++) #define per2(i, l, r) for (int i = (r)-1; i >= (l); i--) #define each(e, v) for (auto &e : v) #define MM << " " << #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; template using minheap = priority_queue, greater>; template using maxheap = priority_queue; template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } template int flg(T x, int i) { return (x >> i) & 1; } template void print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } template void printn(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << '\n'; } template int lb(const vector &v, T x) { return lower_bound(begin(v), end(v), x) - begin(v); } template int ub(const vector &v, T x) { return upper_bound(begin(v), end(v), x) - begin(v); } template void rearrange(vector &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template vector id_sort(const vector &v, bool greater = false) { int n = v.size(); vector ret(n); iota(begin(ret), end(ret), 0); sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; }); return ret; } template pair operator+(const pair &p, const pair &q) { return make_pair(p.first + q.first, p.second + q.second); } template pair operator-(const pair &p, const pair &q) { return make_pair(p.first - q.first, p.second - q.second); } template istream &operator>>(istream &is, pair &p) { S a; T b; is >> a >> b; p = make_pair(a, b); return is; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; const int inf = (1 << 30) - 1; const ll INF = (1LL << 60) - 1; // const int MOD = 1000000007; const int MOD = 998244353; template struct Mod_Int { int x; Mod_Int() : x(0) {} Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} static int get_mod() { return mod; } Mod_Int &operator+=(const Mod_Int &p) { if ((x += p.x) >= mod) x -= mod; return *this; } Mod_Int &operator-=(const Mod_Int &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } Mod_Int &operator*=(const Mod_Int &p) { x = (int)(1LL * x * p.x % mod); return *this; } Mod_Int &operator/=(const Mod_Int &p) { *this *= p.inverse(); return *this; } Mod_Int &operator++() { return *this += Mod_Int(1); } Mod_Int operator++(int) { Mod_Int tmp = *this; ++*this; return tmp; } Mod_Int &operator--() { return *this -= Mod_Int(1); } Mod_Int operator--(int) { Mod_Int tmp = *this; --*this; return tmp; } Mod_Int operator-() const { return Mod_Int(-x); } Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; } Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; } Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; } Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; } bool operator==(const Mod_Int &p) const { return x == p.x; } bool operator!=(const Mod_Int &p) const { return x != p.x; } Mod_Int inverse() const { assert(*this != Mod_Int(0)); return pow(mod - 2); } Mod_Int pow(long long k) const { Mod_Int now = *this, ret = 1; for (; k > 0; k >>= 1, now *= now) { if (k & 1) ret *= now; } return ret; } friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; } friend istream &operator>>(istream &is, Mod_Int &p) { long long a; is >> a; p = Mod_Int(a); return is; } }; using mint = Mod_Int; template struct Number_Theoretic_Transform { static int max_base; static T root; static vector r, ir; Number_Theoretic_Transform() {} static void init() { if (!r.empty()) return; int mod = T::get_mod(); int tmp = mod - 1; root = 2; while (root.pow(tmp >> 1) == 1) root++; max_base = 0; while (tmp % 2 == 0) tmp >>= 1, max_base++; r.resize(max_base), ir.resize(max_base); for (int i = 0; i < max_base; i++) { r[i] = -root.pow((mod - 1) >> (i + 2)); // r[i] := 1 の 2^(i+2) 乗根 ir[i] = r[i].inverse(); // ir[i] := 1/r[i] } } static void ntt(vector &a) { init(); int n = a.size(); assert((n & (n - 1)) == 0); assert(n <= (1 << max_base)); for (int k = n; k >>= 1;) { T w = 1; for (int s = 0, t = 0; s < n; s += 2 * k) { for (int i = s, j = s + k; i < s + k; i++, j++) { T x = a[i], y = w * a[j]; a[i] = x + y, a[j] = x - y; } w *= r[__builtin_ctz(++t)]; } } } static void intt(vector &a) { init(); int n = a.size(); assert((n & (n - 1)) == 0); assert(n <= (1 << max_base)); for (int k = 1; k < n; k <<= 1) { T w = 1; for (int s = 0, t = 0; s < n; s += 2 * k) { for (int i = s, j = s + k; i < s + k; i++, j++) { T x = a[i], y = a[j]; a[i] = x + y, a[j] = w * (x - y); } w *= ir[__builtin_ctz(++t)]; } } T inv = T(n).inverse(); for (auto &e : a) e *= inv; } static vector convolve(vector a, vector b) { if (a.empty() || b.empty()) return {}; int k = (int)a.size() + (int)b.size() - 1, n = 1; while (n < k) n <<= 1; a.resize(n), b.resize(n); ntt(a), ntt(b); for (int i = 0; i < n; i++) a[i] *= b[i]; intt(a), a.resize(k); return a; } }; template int Number_Theoretic_Transform::max_base = 0; template T Number_Theoretic_Transform::root = T(); template vector Number_Theoretic_Transform::r = vector(); template vector Number_Theoretic_Transform::ir = vector(); using NTT = Number_Theoretic_Transform; template struct Combination { static vector _fac, _ifac; Combination() {} static void init(int n) { _fac.resize(n + 1), _ifac.resize(n + 1); _fac[0] = 1; for (int i = 1; i <= n; i++) _fac[i] = _fac[i - 1] * i; _ifac[n] = _fac[n].inverse(); for (int i = n; i >= 1; i--) _ifac[i - 1] = _ifac[i] * i; } static T fac(int k) { return _fac[k]; } static T ifac(int k) { return _ifac[k]; } static T inv(int k) { return fac(k - 1) * ifac(k); } static T P(int n, int k) { if (k < 0 || n < k) return 0; return fac(n) * ifac(n - k); } static T C(int n, int k) { if (k < 0 || n < k) return 0; return fac(n) * ifac(n - k) * ifac(k); } // k 個の区別できない玉を n 個の区別できる箱に入れる場合の数 static T H(int n, int k) { if (n < 0 || k < 0) return 0; return k == 0 ? 1 : C(n + k - 1, k); } // n 個の区別できる玉を、k 個の区別しない箱に、各箱に 1 個以上玉が入るように入れる場合の数 static T second_stirling_number(int n, int k) { T ret = 0; for (int i = 0; i <= k; i++) { T tmp = C(k, i) * T(i).pow(n); ret += ((k - i) & 1) ? -tmp : tmp; } return ret * ifac(k); } // n 個の区別できる玉を、k 個の区別しない箱に入れる場合の数 static T bell_number(int n, int k) { if (n == 0) return 1; k = min(k, n); vector pref(k + 1); pref[0] = 1; for (int i = 1; i <= k; i++) { if (i & 1) { pref[i] = pref[i - 1] - ifac(i); } else { pref[i] = pref[i - 1] + ifac(i); } } T ret = 0; for (int i = 1; i <= k; i++) ret += T(i).pow(n) * ifac(i) * pref[k - i]; return ret; } }; template vector Combination::_fac = vector(); template vector Combination::_ifac = vector(); using comb = Combination; template vector divisors(const T &n) { vector ret; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(begin(ret), end(ret)); return ret; } template vector> prime_factor(T n) { vector> ret; for (T i = 2; i * i <= n; i++) { int cnt = 0; while (n % i == 0) cnt++, n /= i; if (cnt > 0) ret.emplace_back(i, cnt); } if (n > 1) ret.emplace_back(n, 1); return ret; } template bool is_prime(const T &n) { if (n == 1) return false; for (T i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // 1,2,...,n のうち k と互いに素である自然数の個数 template T coprime(T n, T k) { vector> ps = prime_factor(k); int m = ps.size(); T ret = 0; for (int i = 0; i < (1 << m); i++) { T prd = 1; for (int j = 0; j < m; j++) { if ((i >> j) & 1) prd *= ps[j].first; } ret += (__builtin_parity(i) ? -1 : 1) * (n / prd); } return ret; } vector Eratosthenes(const int &n) { vector ret(n + 1, true); if (n >= 0) ret[0] = false; if (n >= 1) ret[1] = false; for (int i = 2; i * i <= n; i++) { if (!ret[i]) continue; for (int j = i + i; j <= n; j += i) ret[j] = false; } return ret; } vector Eratosthenes2(const int &n) { vector ret(n + 1); iota(begin(ret), end(ret), 0); if (n >= 0) ret[0] = -1; if (n >= 1) ret[1] = -1; for (int i = 2; i * i <= n; i++) { if (ret[i] < i) continue; for (int j = i + i; j <= n; j += i) ret[j] = min(ret[j], i); } return ret; } template struct Segment_Tree { using F = function; int n; vector seg; const F f; const Monoid e1; // f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = a Segment_Tree(const vector &v, const F &f, const Monoid &e1) : f(f), e1(e1) { int m = v.size(); n = 1; while (n < m) n <<= 1; seg.assign(2 * n, e1); copy(begin(v), end(v), seg.begin() + n); for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]); } Segment_Tree(int m, const Monoid &x, const F &f, const Monoid &e1) : Segment_Tree(vector(m, x), f, e1) {} void change(int i, const Monoid &x, bool update = true) { if (update) { seg[i + n] = x; } else { seg[i + n] = f(seg[i + n], x); } i += n; while (i >>= 1) seg[i] = f(seg[2 * i], seg[2 * i + 1]); } Monoid query(int l, int r) const { l = max(l, 0), r = min(r, n); Monoid L = e1, R = e1; l += n, r += n; while (l < r) { if (l & 1) L = f(L, seg[l++]); if (r & 1) R = f(seg[--r], R); l >>= 1, r >>= 1; } return f(L, R); } Monoid operator[](int i) const { return seg[n + i]; } template int find_subtree(int i, const C &check, const Monoid &x, Monoid &M, int type) const { while (i < n) { Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]); if (check(nxt, x)) { i = 2 * i + type; } else { M = nxt; i = 2 * i + (type ^ 1); } } return i - n; } // check((区間 [l,r] での演算結果), x) を満たす最小の r (存在しなければ n 以上の値) template int find_first(int l, const C &check, const Monoid &x) const { Monoid L = e1; int a = l + n, b = n + n; while (a < b) { if (a & 1) { Monoid nxt = f(L, seg[a]); if (check(nxt, x)) return find_subtree(a, check, x, L, 0); L = nxt, a++; } a >>= 1, b >>= 1; } return n; } // check((区間 [l,r) での演算結果), x) を満たす最大の l (存在しなければ -1) template int find_last(int r, const C &check, const Monoid &x) const { Monoid R = e1; int a = n, b = r + n; while (a < b) { if ((b & 1) || a == 1) { Monoid nxt = f(seg[--b], R); if (check(nxt, x)) return find_subtree(b, check, x, R, 1); R = nxt; } a >>= 1, b >>= 1; } return -1; } }; struct Union_Find_Tree { vector data; const int n; int cnt; Union_Find_Tree(int n) : data(n, -1), n(n), cnt(n) {} int root(int x) { if (data[x] < 0) return x; return data[x] = root(data[x]); } int operator[](int i) { return root(i); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y], data[y] = x; cnt--; return true; } int size(int x) { return -data[root(x)]; } int count() { return cnt; }; bool same(int x, int y) { return root(x) == root(y); } void clear() { cnt = n; fill(begin(data), end(data), -1); } }; template struct Sparse_Table { using F = function; const int n; int height; vector> st; // st[i][j] := 区間 [j,j+2^i) での演算の結果 vector lookup; const F f; const T e; // f(f(a,b),c) = f(a,f(b,c)), f(e,a) = f(a,e) = a, f(a,a) = a // 例えば min や gcd はこれらを満たすが、+ や * は満たさない Sparse_Table(const vector &table, const F &f, const T &e) : n((int)table.size()), f(f), e(e) { height = 0; while (n >> height) height++; st.assign(height, vector(n)); for (int i = 0; i < n; i++) st[0][i] = table[i]; for (int j = 0; j < height - 1; j++) { for (int i = 0; i < n; i++) { if (i + (1 << j) < n) { st[j + 1][i] = f(st[j][i], st[j][i + (1 << j)]); } else { st[j + 1][i] = st[j][i]; } } } lookup.assign(n + 1, -1); for (int i = 1; i <= n; i++) lookup[i] = lookup[i / 2] + 1; } T query(int l, int r) const { if (l >= r) return e; int k = lookup[r - l]; return f(st[k][l], st[k][r - (1 << k)]); } T operator[](int i) const { return st[0][i]; } }; template struct Low_Link { struct edge { int to, id; edge(int to, int id) : to(to), id(id) {} }; vector> es; vector ord, low; vector used; vector articulation, bridge; const int n; int m; Low_Link(int n) : es(n), ord(n), low(n), used(n), n(n), m(0) {} void add_edge(int from, int to) { es[from].emplace_back(to, m); if (!directed) es[to].emplace_back(from, m); m++; } int _dfs(int now, int pre, int k) { used[now] = true; ord[now] = low[now] = k++; bool is_articulation = false; int cnt = 0; for (auto &e : es[now]) { if (e.id == pre) continue; if (!used[e.to]) { cnt++; k = _dfs(e.to, e.id, k); low[now] = min(low[now], low[e.to]); if (pre != -1 && low[e.to] >= ord[now]) is_articulation = true; if (ord[now] < low[e.to]) bridge.push_back(e.id); } else { low[now] = min(low[now], ord[e.to]); } } if (pre == -1 && cnt >= 2) is_articulation = true; if (is_articulation) articulation.push_back(now); return k; } void build() { fill(begin(used), end(used), false); int k = 0; for (int i = 0; i < n; i++) { if (!used[i]) k = _dfs(i, -1, k); } } }; template struct Biconnected_Components : Low_Link { using L = Low_Link; vector comp; vector used; const int n; Biconnected_Components(int n) : L(n), used(n), n(n) {} int _dfs(int now, int pre, int top, int k) { used[now] = true; for (auto &e : this->es[now]) { if (comp[e.id] != -1) continue; if (this->ord[e.to] < this->ord[now]) { comp[e.id] = top; } else if (this->low[e.to] >= this->ord[now]) { comp[e.id] = k; k = _dfs(e.to, now, k, k + 1); } else { comp[e.id] = top; k = _dfs(e.to, now, top, k); } } return k; } int decompose() { this->build(); comp.assign(this->m, -1); fill(begin(used), end(used), false); int k = 0; for (int i = 0; i < n; i++) { if (!used[i]) k = _dfs(i, -1, -1, k); } return k; } }; template void fast_zeta_transform(vector &a, bool upper) { int n = a.size(); assert((n & (n - 1)) == 0); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if (!(j & i)) { if (upper) { a[j] += a[j | i]; } else { a[j | i] += a[j]; } } } } } template void fast_mobius_transform(vector &a, bool upper) { int n = a.size(); assert((n & (n - 1)) == 0); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if (!(j & i)) { if (upper) { a[j] -= a[j | i]; } else { a[j | i] -= a[j]; } } } } } template void fast_hadamard_transform(vector &a, bool inverse = false) { int n = a.size(); assert((n & (n - 1)) == 0); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if (!(j & i)) { T x = a[j], y = a[j | i]; a[j] = x + y, a[j | i] = x - y; } } } if (inverse) { T inv = T(1) / T(n); for (auto &e : a) e *= inv; } } template vector bitwise_and_convolve(vector a, vector b) { int n = a.size(); assert(b.size() == n && (n & (n - 1)) == 0); fast_zeta_transform(a, true), fast_zeta_transform(b, true); for (int i = 0; i < n; i++) a[i] *= b[i]; fast_mobius_transform(a, true); return a; } template vector bitwise_or_convolve(vector a, vector b) { int n = a.size(); assert(b.size() == n && (n & (n - 1)) == 0); fast_zeta_transform(a, false), fast_zeta_transform(b, false); for (int i = 0; i < n; i++) a[i] *= b[i]; fast_mobius_transform(a, false); return a; } template vector bitwise_xor_convolve(vector a, vector b) { int n = a.size(); assert(b.size() == n && (n & (n - 1)) == 0); fast_hadamard_transform(a), fast_hadamard_transform(b); for (int i = 0; i < n; i++) a[i] *= b[i]; fast_hadamard_transform(a, true); return a; } template vector subset_convolve(const vector &a, const vector &b) { int n = a.size(); assert(b.size() == n && (n & (n - 1)) == 0); int k = __builtin_ctz(n); vector> A(k + 1, vector(n, 0)), B(k + 1, vector(n, 0)), C(k + 1, vector(n, 0)); for (int i = 0; i < n; i++) { int t = __builtin_popcount(i); A[t][i] = a[i], B[t][i] = b[i]; } for (int i = 0; i <= k; i++) fast_zeta_transform(A[i], false), fast_zeta_transform(B[i], false); for (int i = 0; i <= k; i++) { for (int j = 0; j <= k - i; j++) { for (int l = 0; l < n; l++) C[i + j][l] += A[i][l] * B[j][l]; } } for (int i = 0; i <= k; i++) fast_mobius_transform(C[i], false); vector c(n); for (int i = 0; i < n; i++) c[i] = C[__builtin_popcount(i)][i]; return c; } template void divisors_zeta_transform(vector &a, bool upper) { int n = a.size(); vector is_prime(n, true); if (!upper) { for (int i = 1; i < n; i++) a[0] += a[i]; } for (int i = 2; i < n; i++) { if (!is_prime[i]) continue; if (upper) { for (int j = (n - 1) / i; j > 0; j--) { is_prime[j * i] = false; a[j] += a[j * i]; } } else { for (int j = 1; j * i < n; j++) { is_prime[j * i] = false; a[j * i] += a[j]; } } } if (upper) { for (int i = 1; i < n; i++) a[i] += a[0]; } } template void divisors_mobius_transform(vector &a, bool upper) { int n = a.size(); vector is_prime(n, true); if (upper) { for (int i = 1; i < n; i++) a[i] -= a[0]; } for (int i = 2; i < n; i++) { if (!is_prime[i]) continue; if (upper) { for (int j = 1; j * i < n; j++) { is_prime[j * i] = false; a[j] -= a[j * i]; } } else { for (int j = (n - 1) / i; j > 0; j--) { is_prime[j * i] = false; a[j * i] -= a[j]; } } } if (!upper) { for (int i = 1; i < n; i++) a[0] -= a[i]; } } void solve() {} int main() { int N, M; cin >> N >> M; vector cnt(M + 1, 0); rep(i, N) { int x; cin >> x; cnt[x]++; } vector a(M + 1, 0); rep2(i, 1, M + 1) { int c = 0; for (int j = i; j <= M; j += i) c += cnt[j]; a[i] = mint(2).pow(c) - 1; } divisors_mobius_transform(a, true); rep2(i, 1, M + 1) cout << a[i] << '\n'; }