#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; using mint = modint998244353; constexpr int FACT_SIZE = 1000000; mint Fact[FACT_SIZE + 1]; mint iFact[FACT_SIZE + 1]; const auto fact_init = [] { Fact[0] = mint::raw(1); for(int i = 1; i <= FACT_SIZE; ++i) { Fact[i] = Fact[i-1] * i; } iFact[FACT_SIZE] = Fact[FACT_SIZE].inv(); for(int i = FACT_SIZE; i; --i) { iFact[i-1] = iFact[i] * i; } return false; }(); mint comb(int n, int k) { if (k == 0) return mint::raw(1); assert(n >= 0 && k >= 0); if (k > n) return mint::raw(0); return Fact[n] * iFact[n - k] * iFact[k]; } mint icomb(int n, int k) { return iFact[n] * Fact[n - k] * Fact[k]; } mint fact(int n) {return Fact[n];} mint perm(int n, int k) { assert(0 <= n); return Fact[n] * iFact[n - k]; } template struct FPS : vector { using vector::vector; FPS& operator+=(const FPS& f) { const int tsz = this->size(), fsz = f.size(); const int csz = min(tsz, fsz); for (int i = 0; i < csz; i++) (*this)[i] += f[i]; if (csz < fsz) { this->insert(this->end(), f.begin() + csz, f.end()); } return *this; } FPS& operator+=(FPS&& f) { if (this->size() < f.size()) swap(*this, f); *this += f; return *this; } friend FPS operator+(const FPS& f, const FPS& g) { FPS h; h.reserve(max(f.size(), g.size())); h = f; h += g; return h; } friend FPS operator+(FPS&& f, const FPS& g) { return move(f += g); } friend FPS operator+(const FPS& f, FPS&& g) { return move(g += f); } friend FPS operator+(FPS&& f, FPS&& g) { return move(f += move(g)); } FPS& operator-=(const FPS& f) { const int tsz = this->size(), fsz = f.size(); const int csz = min(tsz, fsz); for (int i = 0; i < csz; i++) (*this)[i] -= f[i]; if (csz < fsz) { this->resize(fsz); for (int i = csz; i < fsz; i++) (*this)[i] = -f[i]; } return *this; } FPS& operator-=(FPS&& f) { const int tsz = this->size(), fsz = f.size(); if (tsz > fsz) { *this -= f; } else { for (int i = 0; i < tsz; i++) f[i] = (*this)[i] - f[i]; for (int i = tsz; i < fsz; i++) f[i] = -f[i]; swap(*this, f); } return *this; } friend FPS operator-(const FPS& f, const FPS& g) { FPS h; h.reserve(max(f.size(), g.size())); h = f; h -= g; return h; } friend FPS operator-(FPS&& f, const FPS& g) { return move(f -= g); } friend FPS operator-(const FPS& f, FPS&& g) { const int fsz = f.size(), gsz = g.size(); const int csz = min(fsz, gsz); for (int i = 0; i < csz; i++) g[i] = f[i] - g[i]; if (fsz < gsz) { for (int i = csz; i < gsz; i++) g[i] = -g[i]; } else { g.insert(g.end(), f.begin() + csz, f.end()); } return move(g); } friend FPS operator-(FPS&& f, FPS&& g) { return move(f -= move(g)); } FPS operator+() && { return move(*this); } FPS operator+() const& { return *this; } FPS operator-() && { for (T& x: *this) x = -x; return move(*this); } FPS operator-() const& { FPS f; f.reserve(this->size()); for (const T& x: *this) f.emplace_back(-x); return f; } static void multiply_naive(FPS& f, const FPS& g) { int n = int(f.size()), m = int(g.size()); if (n < m) { tmp1 = f; f.assign(n + m - 1, T()); for (int j = m - 1; j >= 0; j--) { for (int i = n - 1; i >= 0; i--) { f[i + j] += tmp1[i] * g[j]; } } } else { f.resize(n + m - 1); for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j > 0; j--) { f[i + j] += f[i] * g[j]; } f[i] *= g[0]; } } } static void multiply_fft(FPS& f, const FPS& g) { const int n = f.size(), m = g.size(); const int z = bit_ceil(0U + n + m - 1); tmp1.reserve(z), tmp1 = g, tmp1.resize(z), internal::butterfly(tmp1); f.resize(z), internal::butterfly(f); for (int i = 0; i < z; i++) f[i] *= tmp1[i]; internal::butterfly_inv(f); f.resize(n + m - 1); mint iz = mint(z).inv(); for (int i = 0; i < n + m - 1; i++) f[i] *= iz; } FPS& operator*=(const FPS& f) { int n = int((*this).size()), m = int(f.size()); if (!n || !m) { this->clear(); return *this; }; if (min(n, m) <= 60) multiply_naive(*this, f); else multiply_fft(*this, f); return *this; } FPS& operator*=(FPS&& f) { int n = int((*this).size()), m = int(f.size()); if (this->size() < f.size()) swap(*this, f); return *this *= f; } friend FPS operator*(FPS&& f, FPS&& g) { return move(f *= move(g)); } friend FPS operator*(FPS&& f, const FPS& g) { return move(f *= g); } friend FPS operator*(const FPS& f, FPS&& g) { return move(g *= f); } friend FPS operator*(const FPS& f, const FPS& g) { int n = int(f.size()), m = int(g.size()); if (!n || !m) return {}; int z = bit_ceil(0U + n + m - 1); FPS h; h.reserve(z); h = f; h *= g; return h; } FPS& operator+=(T x) { if ((*this).empty()) (*this).emplace_back(x); else (*this)[0] += x; return *this; } friend FPS operator+(FPS f, T x) { f += x; return f; } friend FPS operator+(T x, FPS f) { f += x; return f; } FPS& operator-=(T x) { if ((*this).empty()) (*this).emplace_back(-x); else (*this)[0] -= x; return *this; } friend FPS operator-(FPS f, T x) { f -= x; return f; } friend FPS operator-(T x, FPS f) { return -move(f) + x; } FPS& operator*=(T x) { for (T& i: *this) i *= x; return *this; } friend FPS operator*(FPS f, T x) { f *= x; return f; } friend FPS operator*(T x, FPS f) { f *= x; return f; } FPS operator/=(T x) { if constexpr (internal::is_modint::value) { T ix = x.inv(); for (T& i: *this) i *= ix; } else { for (T& i: *this) i /= x; } return *this; } friend FPS operator/(FPS f, T x) { f /= x; return f; } FPS& operator<<=(int x) { assert(x >= 0); this->insert((*this).begin(), x, T()); return *this; } friend FPS operator<<(const FPS& f, int x) { assert(x >= 0); const int fsz = f.size(); FPS res; res.reserve(fsz + x); res.resize(x); res.insert(res.end(), f.begin(), f.end()); return res; } friend FPS operator<<(FPS&& f, int x) { f <<= x; return move(f); } FPS& operator>>=(int x) { assert(x >= 0); const int tsz = this->size(); if (x >= tsz) this->clear(); else this->erase(this->begin(), this->begin() + x); return *this; } friend FPS operator>>(const FPS& f, int x) { assert(x >= 0); const int fsz = f.size(); if (x >= fsz) return {}; else return FPS(f.begin() + x, f.end()); } friend FPS operator>>(FPS&& f, int x) { f >>= x; return move(f); } static FPS inv_proc(const FPS& f, FPS g, int len) { if (len == 0) { g.clear(); return g; } FPS fi, gi; swap(fi, tmp2); swap(gi, tmp3); const int z = bit_ceil(0U + len); const int n = f.size(); g.clear(); g.reserve(z); fi.reserve(z); gi.reserve(z); assert(len >= 1 && n >= 1 && f[0] != 0); g.emplace_back(f[0] != 1 ? f[0].inv() : f[0]); const T inv2 = T(1) / 2; T i2k = 1; int m = 1; while (m != z) { const int m2 = 2 * m; fi.assign(f.begin(), f.begin() + min(n, m2)); fi.resize(m2); internal::butterfly(fi); gi = g; gi.resize(m2); internal::butterfly(gi); for (int i = 0; i < m2; i++) fi[i] *= gi[i]; internal::butterfly_inv(fi); fi.erase(fi.begin(), fi.begin() + m); fi.resize(m2); internal::butterfly(fi); for (int i = 0; i < m2; i++) fi[i] *= gi[i]; internal::butterfly_inv(fi); i2k *= inv2; T c = -i2k * i2k; for (int i = 0; i < m; i++) { g.emplace_back(c * fi[i]); } m = m2; } g.resize(len); swap(fi, tmp2); swap(gi, tmp3); return g; } FPS inv(int len) const& { return inv_proc(*this, FPS(), len); } FPS inv(int len) && { tmp1 = *this; return inv_proc(tmp1, move(*this), len); } void Taylor_Shift_inplace(T c) { const int n = this->size(); FPS f, g; swap(g, tmp2); swap(f, tmp3); f = *this; for (int i = 0; i < n; i++) f[i] *= Fact[i]; T ck = 1; g.resize(n); for (int i = 0, j = n - 1; i < n; i++, j--, ck *= c) g[j] = ck * iFact[i]; f *= g; for (int i = 0, j = n - 1; i < n; i++, j++) (*this)[i] = iFact[i] * f[j]; swap(g, tmp2); swap(f, tmp3); } FPS Taylor_Shift(T c) const& { return FPS(*this).Taylor_Shift(c); } FPS Taylor_Shift(T c) && { this->Taylor_Shift_inplace(c); return move(*this); } void show(char sep = ' ', char end = '\n', bool flush = false) const { int sz = this->size(); if (sz) { cout << (*this)[0].val(); for (int i = 1; i < sz; i++) cout << sep << (*this)[i].val(); } cout << end; if (flush) cout.flush(); } private: inline static FPS tmp1, tmp2, tmp3; }; } int main() { ios::sync_with_stdio(false); cin.tie(0); using fps = FPS; int n, k; cin >> n >> k; k++; fps f(n + 1); for (int i = 0;; i++) { int v = i * (3 * i - 1) / 2; if (v > n) break; f[v] = i % 2 ? -1 : 1; } for (int i = -1;; i--) { int v = i * (3 * i - 1) / 2; if (v > n) break; f[v] = i % 2 ? -1 : 1; } fps p(n + 1); for (int i = 0; i * k <= n; i++) p[i * k] = f[i]; p *= f.inv(n + 1); for (int x = 1; x <= n; x++) cout << p[x].val() << " \n"[x == n]; }