#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 998244353;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
namespace Poly {
vector<int> roots, rev;
void getRevRoot(int base) {
  int n = 1 << base;
  if ((int)rev.size() == n) return;
  rev.resize(n);
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
  if ((int)roots.size() >= n) return;
  int pren = max(1, (int)roots.size());
  roots.resize(n);
  for (int mid = pren; mid < n; mid <<= 1) {
    int wn = fpow(3, (md - 1) / (mid << 1));
    roots[mid] = 1;
    for (int i = 1; i < mid; i++) roots[i + mid] = mul(roots[i + mid - 1], wn);
  }
}
void ntt(vector<int> &a, int base) {
  int n = 1 << base;
  for (int i = 0; i < n; i++) {
    if (i < rev[i]) {
      swap(a[i], a[rev[i]]);
    }
  }
  for (int mid = 1; mid < n; mid <<= 1) {
    for (int i = 0; i < n; i += (mid << 1)) {
      for (int j = 0; j < mid; j++) {
        int x = a[i + j], y = mul(a[i + j + mid], roots[mid + j]);
        a[i + j] = add(x, y);
        a[i + j + mid] = sub(x, y);
      }
    }
  }
}
vector<int> operator*(vector<int> a, vector<int> b) {
  if ((int)a.size() <= 64 && (int)b.size() <= 64) {
    vector<int> ans(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int)a.size(); i++) {
      for (int j = 0; j < (int)b.size(); j++) {
        ans[i + j] = add(ans[i + j], mul(a[i], b[j]));
      }
    }
    return ans;
  }
  int n = (int)a.size() + (int)b.size() - 1, base = 0;
  while ((1 << base) < n) ++base;
  a.resize(1 << base);
  b.resize(1 << base);
  getRevRoot(base);
  ntt(a, base);
  ntt(b, base);
  for (int i = 0; i < (1 << base); i++) a[i] = mul(a[i], b[i]);
  reverse(a.begin() + 1, a.end());
  ntt(a, base);
  a.resize(n);
  int inv = fpow(1 << base, md - 2);
  for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
  return a;
}
vector<int> tmp;
vector<int> pmul(vector<int> a, vector<int> b, int n, int ntted = 0) {
  int base = 0;
  while ((1 << base) < n) ++base;
  getRevRoot(base);
  a.resize(1 << base);
  ntt(a, base);
  if (!ntted) b.resize(1 << base), ntt(b, base), tmp = b;
  for (int i = 0; i < (1 << base); i++) a[i] = mul(a[i], tmp[i]);
  ntt(a, base);
  reverse(a.begin() + 1, a.end());
  a.resize(n);
  int inv = fpow(1 << base, md - 2);
  for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
  return a;
}
vector<int> polyInv(vector<int> a, int n) {
  a.resize(n);
  if (n == 1) {
    vector<int> ans(1, fpow(a[0], md - 2));
    return ans;
  }
  vector<int> f0 = polyInv(a, (n + 1) >> 1), ans = f0;
  vector<int> now = pmul(a, f0, n, 0);
  for (int i = 0; i < (int)f0.size(); i++) now[i] = 0;
  now = pmul(now, vector<int>(0), n, 1);
  ans.resize(n);
  for (int i = (int)f0.size(); i < n; i++) ans[i] = sub(0, now[i]);
  return ans;
}
vector<int> polyInv(vector<int> a) { return polyInv(a, (int)a.size()); }
vector<int> operator+(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < (int)b.size(); i++) a[i] = add(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < (int)b.size(); i++) a[i] = sub(a[i], b[i]);
  return a;
}
vector<int> diff(vector<int> f) {
  int n = (int)f.size() - 1;
  for (int i = 0; i < n; i++) f[i] = mul(f[i + 1], i + 1);
  f.resize(n);
  return f;
}
vector<int> inte(vector<int> f) {
  int n = (int)f.size() + 1;
  f.resize(n);
  for (int i = n - 1; i >= 1; i--) f[i] = mul(f[i - 1], fpow(i, md - 2));
  f[0] = 0;
  return f;
}
vector<int> polyLn(vector<int> f) {
  int n = (int)f.size();
  f = inte(diff(f) * polyInv(f));
  f.resize(n);
  return f;
}
vector<int> polyExp(vector<int> f, int base) {
  int n = 1 << base;
  f.resize(n);
  if (n == 1) {
    vector<int> ans(1, 1);
    return ans;
  }
  vector<int> g0 = polyExp(f, base - 1), g(1, 1);
  g0.resize(n);
  g = g0 * (g - polyLn(g0) + f);
  return g;
}
vector<int> polyExp(vector<int> f) {
  int n = (int)f.size(), base = 0;
  while ((1 << base) < n) ++base;
  f = polyExp(f, base);
  f.resize(n);
  return f;
}
}  // namespace Poly
using Poly::operator*;
using Poly::diff;
using Poly::polyExp;
using Poly::polyInv;
using Poly::polyLn;
const int N = 1e5 + 5;
vector<int> G, LG, F, H;
int fac[N], inv[N], ans[N], h[N];
int n;
inline int getinv(int x) { return mul(fac[x - 1], inv[x]); }
vector<int> getpow(vector<int> x, int y) {
  x = polyLn(x);
  for (int i = 0; i < (int)x.size(); i++) x[i] = mul(x[i], y);
  x = polyExp(x);
  return x;
}
int main() {
  fac[0] = 1;
  for (int i = 1; i <= 100002; i++) fac[i] = mul(fac[i - 1], i);
  inv[100002] = fpow(fac[100002], md - 2);
  for (int i = 100002; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
  read(n);
  G.resize(n + 3);
  LG.resize(n + 2);
  for (int i = 1; i <= n + 2; i++) {
    G[i] = getinv(i);
    if (i % 2 == 0) G[i] = md - G[i];
  }
  for (int i = 0; i <= n + 1; i++) LG[i] = G[i + 1];
  vector<int> res = polyInv(LG);
  for (int i = 0; i <= n + 1; i++) res[i] = sub(0, res[i]);
  for (int i = 0; i <= n; i++) res[i] = res[i + 1];
  res.resize(n + 1);
  res = polyInv(res);
  res = res * diff(G);
  res.resize(n + 1);
  res = res * getpow(polyInv(LG), n + 2);
  res.resize(n + 1);
  for (int i = 0; i < n; i++) res[i] = res[i + 1];
  for (int i = 0; i < n; i++) h[i] = sub(h[i], res[i]);
  vector<int> P;
  P.resize(n + 1);
  for (int i = 0; i <= n; i++) P[i] = md - inv[i + 2];
  P = polyInv(P);
  for (int i = 0; i < n; i++) h[i] = add(h[i], P[i + 1]);
  h[0] = sub(h[0], 1);
  F.resize(n);
  H.resize(n);
  for (int i = 0; i < n; i++) {
    F[i] = mul(h[i], fac[i]);
    H[i] = inv[i];
    if (i & 1) {
      H[i] = sub(0, H[i]);
    }
  }
  reverse(H.begin(), H.end());
  F = F * H;
  for (int i = 0; i < n; i++) ans[i + 1] = mul(F[i + n - 1], inv[i]);
  for (int i = 1; i <= n; i++) print(mul(ans[i], fac[n]), i == n ? '\n' : ' ');
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Note that the only differences between easy and hard versions are the constraints on n and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences p of length n as follows:

  * For each k>1 that presents in p, there should be at least one pair of indices i,j, such that 1 ≤ i < j ≤ n, p_i = k - 1 and p_j = k.



For the given integer n, the set of all good sequences of length n is s_n. For the fixed integer k and the sequence p, let f_p(k) be the number of times that k appears in p. For each k from 1 to n, Slime wants to know the following value:

$$$\left(∑_{p∈ s_n} f_p(k)\right)\ mod\ 998 244 353$$$

Input

The first line contains one integer n\ (1≤ n≤ 100 000).

Output

Print n integers, the i-th of them should be equal to \left(∑_{p∈ s_n} f_p(i)\right)\ mod\ 998 244 353.

Examples

Input


2


Output


3 1 


Input


3


Output


10 7 1 


Input


1


Output


1 

Note

In the first example, s=\{[1,1],[1,2]\}.

In the second example, s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}.

In the third example, s=\{[1]\}.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 998244353;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
namespace Poly {
vector<int> roots, rev;
void getRevRoot(int base) {
  int n = 1 << base;
  if ((int)rev.size() == n) return;
  rev.resize(n);
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
  if ((int)roots.size() >= n) return;
  int pren = max(1, (int)roots.size());
  roots.resize(n);
  for (int mid = pren; mid < n; mid <<= 1) {
    int wn = fpow(3, (md - 1) / (mid << 1));
    roots[mid] = 1;
    for (int i = 1; i < mid; i++) roots[i + mid] = mul(roots[i + mid - 1], wn);
  }
}
void ntt(vector<int> &a, int base) {
  int n = 1 << base;
  for (int i = 0; i < n; i++) {
    if (i < rev[i]) {
      swap(a[i], a[rev[i]]);
    }
  }
  for (int mid = 1; mid < n; mid <<= 1) {
    for (int i = 0; i < n; i += (mid << 1)) {
      for (int j = 0; j < mid; j++) {
        int x = a[i + j], y = mul(a[i + j + mid], roots[mid + j]);
        a[i + j] = add(x, y);
        a[i + j + mid] = sub(x, y);
      }
    }
  }
}
vector<int> operator*(vector<int> a, vector<int> b) {
  if ((int)a.size() <= 64 && (int)b.size() <= 64) {
    vector<int> ans(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int)a.size(); i++) {
      for (int j = 0; j < (int)b.size(); j++) {
        ans[i + j] = add(ans[i + j], mul(a[i], b[j]));
      }
    }
    return ans;
  }
  int n = (int)a.size() + (int)b.size() - 1, base = 0;
  while ((1 << base) < n) ++base;
  a.resize(1 << base);
  b.resize(1 << base);
  getRevRoot(base);
  ntt(a, base);
  ntt(b, base);
  for (int i = 0; i < (1 << base); i++) a[i] = mul(a[i], b[i]);
  reverse(a.begin() + 1, a.end());
  ntt(a, base);
  a.resize(n);
  int inv = fpow(1 << base, md - 2);
  for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
  return a;
}
vector<int> tmp;
vector<int> pmul(vector<int> a, vector<int> b, int n, int ntted = 0) {
  int base = 0;
  while ((1 << base) < n) ++base;
  getRevRoot(base);
  a.resize(1 << base);
  ntt(a, base);
  if (!ntted) b.resize(1 << base), ntt(b, base), tmp = b;
  for (int i = 0; i < (1 << base); i++) a[i] = mul(a[i], tmp[i]);
  ntt(a, base);
  reverse(a.begin() + 1, a.end());
  a.resize(n);
  int inv = fpow(1 << base, md - 2);
  for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
  return a;
}
vector<int> polyInv(vector<int> a, int n) {
  a.resize(n);
  if (n == 1) {
    vector<int> ans(1, fpow(a[0], md - 2));
    return ans;
  }
  vector<int> f0 = polyInv(a, (n + 1) >> 1), ans = f0;
  vector<int> now = pmul(a, f0, n, 0);
  for (int i = 0; i < (int)f0.size(); i++) now[i] = 0;
  now = pmul(now, vector<int>(0), n, 1);
  ans.resize(n);
  for (int i = (int)f0.size(); i < n; i++) ans[i] = sub(0, now[i]);
  return ans;
}
vector<int> polyInv(vector<int> a) { return polyInv(a, (int)a.size()); }
vector<int> operator+(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < (int)b.size(); i++) a[i] = add(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (int i = 0; i < (int)b.size(); i++) a[i] = sub(a[i], b[i]);
  return a;
}
vector<int> diff(vector<int> f) {
  int n = (int)f.size() - 1;
  for (int i = 0; i < n; i++) f[i] = mul(f[i + 1], i + 1);
  f.resize(n);
  return f;
}
vector<int> inte(vector<int> f) {
  int n = (int)f.size() + 1;
  f.resize(n);
  for (int i = n - 1; i >= 1; i--) f[i] = mul(f[i - 1], fpow(i, md - 2));
  f[0] = 0;
  return f;
}
vector<int> polyLn(vector<int> f) {
  int n = (int)f.size();
  f = inte(diff(f) * polyInv(f));
  f.resize(n);
  return f;
}
vector<int> polyExp(vector<int> f, int base) {
  int n = 1 << base;
  f.resize(n);
  if (n == 1) {
    vector<int> ans(1, 1);
    return ans;
  }
  vector<int> g0 = polyExp(f, base - 1), g(1, 1);
  g0.resize(n);
  g = g0 * (g - polyLn(g0) + f);
  return g;
}
vector<int> polyExp(vector<int> f) {
  int n = (int)f.size(), base = 0;
  while ((1 << base) < n) ++base;
  f = polyExp(f, base);
  f.resize(n);
  return f;
}
}  // namespace Poly
using Poly::operator*;
using Poly::diff;
using Poly::polyExp;
using Poly::polyInv;
using Poly::polyLn;
const int N = 1e5 + 5;
vector<int> G, LG, F, H;
int fac[N], inv[N], ans[N], h[N];
int n;
inline int getinv(int x) { return mul(fac[x - 1], inv[x]); }
vector<int> getpow(vector<int> x, int y) {
  x = polyLn(x);
  for (int i = 0; i < (int)x.size(); i++) x[i] = mul(x[i], y);
  x = polyExp(x);
  return x;
}
int main() {
  fac[0] = 1;
  for (int i = 1; i <= 100002; i++) fac[i] = mul(fac[i - 1], i);
  inv[100002] = fpow(fac[100002], md - 2);
  for (int i = 100002; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
  read(n);
  G.resize(n + 3);
  LG.resize(n + 2);
  for (int i = 1; i <= n + 2; i++) {
    G[i] = getinv(i);
    if (i % 2 == 0) G[i] = md - G[i];
  }
  for (int i = 0; i <= n + 1; i++) LG[i] = G[i + 1];
  vector<int> res = polyInv(LG);
  for (int i = 0; i <= n + 1; i++) res[i] = sub(0, res[i]);
  for (int i = 0; i <= n; i++) res[i] = res[i + 1];
  res.resize(n + 1);
  res = polyInv(res);
  res = res * diff(G);
  res.resize(n + 1);
  res = res * getpow(polyInv(LG), n + 2);
  res.resize(n + 1);
  for (int i = 0; i < n; i++) res[i] = res[i + 1];
  for (int i = 0; i < n; i++) h[i] = sub(h[i], res[i]);
  vector<int> P;
  P.resize(n + 1);
  for (int i = 0; i <= n; i++) P[i] = md - inv[i + 2];
  P = polyInv(P);
  for (int i = 0; i < n; i++) h[i] = add(h[i], P[i + 1]);
  h[0] = sub(h[0], 1);
  F.resize(n);
  H.resize(n);
  for (int i = 0; i < n; i++) {
    F[i] = mul(h[i], fac[i]);
    H[i] = inv[i];
    if (i & 1) {
      H[i] = sub(0, H[i]);
    }
  }
  reverse(H.begin(), H.end());
  F = F * H;
  for (int i = 0; i < n; i++) ans[i + 1] = mul(F[i + n - 1], inv[i]);
  for (int i = 1; i <= n; i++) print(mul(ans[i], fac[n]), i == n ? '\n' : ' ');
  return 0;
}

```