#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, g = 3, invg = (mod + 1) / 3;
int n;
const int maxn = 2e5 + 100;
int ni[maxn], fact[maxn], ifact[maxn], tw[maxn];
int power(int a, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) {
      ret = 1LL * ret * a % mod;
    }
    b /= 2;
    a = 1LL * a * a % mod;
  }
  return ret;
}
vector<int> operator+(vector<int> a, vector<int> b) {
  int t = max((int)a.size(), (int)b.size());
  vector<int> res(t);
  for (int i = 0; i < t; i++) {
    res[i] = ((i < (int)a.size() ? a[i] : 0) + (i < (int)b.size() ? b[i] : 0));
    if (res[i] >= mod) {
      res[i] -= mod;
    }
  }
  return res;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  for (int i = 0; i < (int)b.size(); i++) {
    b[i] = b[i] == 0 ? 0 : (mod - b[i]);
  }
  return a + b;
}
vector<int> operator*(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size(); i++) {
    a[i] = 1LL * a[i] * b % mod;
  }
  return a;
}
vector<int> operator>>(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size() - b; i++) {
    a[i] = a[i + b];
  }
  a.resize((int)a.size() - b);
  return a;
}
namespace poly {
int N, l;
int pre1[20][1100000], pre2[20][1100000], A[1100000], B[1100000], r[1100000];
void pre() {
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = power(g, (mod - 1) / (i << 1));
    for (int j = 0; j < i; j++) {
      pre1[r][j] = w;
      w = 1LL * w * wn % mod;
    }
  }
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = power(invg, (mod - 1) / (i << 1));
    for (int j = 0; j < i; j++) {
      pre2[r][j] = w;
      w = 1LL * w * wn % mod;
    }
  }
}
void ntt(int *A, int n, int f) {
  for (int i = 0; i < n; i++) {
    if (i < r[i]) {
      swap(A[i], A[r[i]]);
    }
  }
  for (int i = 1, j = 0; i < n; i <<= 1, j++) {
    for (int l = 0; l < n; l += (i << 1)) {
      for (int k = 0; k < i; k++) {
        int x = A[l + k];
        int y = 1LL * A[l + k + i] * (f > 0 ? pre1[j][k] : pre2[j][k]) % mod;
        A[l + k] = (x + y);
        if (A[l + k] >= mod) {
          A[l + k] -= mod;
        }
        A[l + k + i] = (x - y + mod);
        while (A[l + k + i] >= mod) {
          A[l + k + i] -= mod;
        }
      }
    }
  }
  if (f < 0) {
    int inv_n = power(n, mod - 2);
    for (int i = 0; i < n; i++) {
      A[i] = 1LL * A[i] * inv_n % mod;
    }
  }
}
void init(int t) {
  N = 1, l = 0;
  while (N < t) {
    l++;
    N <<= 1;
  }
  for (int i = 0; i < N; i++) {
    r[i] = ((r[i >> 1] >> 1) | ((i & 1) ? (N >> 1) : 0));
  }
}
void getmul() {
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) {
    A[i] = 1LL * A[i] * B[i] % mod;
  }
  ntt(A, N, -1);
}
vector<int> mul(vector<int> a, vector<int> b) {
  init((int)a.size() + (int)b.size());
  for (int i = 0; i < N; i++) {
    A[i] = ((i < (int)a.size()) ? a[i] : 0);
  }
  for (int i = 0; i < N; i++) {
    B[i] = ((i < (int)b.size()) ? b[i] : 0);
  }
  getmul();
  vector<int> ret((int)a.size() + (int)b.size() - 1);
  for (int i = 0; i < (int)ret.size(); i++) {
    ret[i] = A[i];
  }
  return ret;
}
vector<int> polyinv(vector<int> a, int l) {
  if (l == 1) {
    return vector<int>(1, power(a[0], mod - 2));
  }
  a.resize(l);
  vector<int> b = polyinv(a, (l + 1) / 2);
  init(l << 1);
  for (int i = 0; i < N; i++) {
    A[i] = (i < l ? a[i] : 0);
  }
  for (int i = 0; i < N; i++) {
    B[i] = (i < (l + 1) / 2 ? b[i] : 0);
  }
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) {
    A[i] = 1LL * A[i] * B[i] % mod * B[i] % mod;
  }
  ntt(A, N, -1);
  vector<int> t = b * 2;
  t.resize(l);
  for (int i = 0; i < l; i++) {
    t[i] = (t[i] + mod - A[i]);
    if (t[i] >= mod) {
      t[i] -= mod;
    }
  }
  return t;
}
vector<int> polydiff(vector<int> a) {
  for (int i = 0; i < (int)a.size() - 1; i++) {
    a[i] = 1LL * (i + 1) * a[i + 1] % mod;
  }
  a.resize((int)a.size() - 1);
  return a;
}
vector<int> polyint(vector<int> a) {
  a.resize((int)a.size() + 1);
  for (int i = (int)a.size() - 1; i >= 1; i--) {
    a[i] = 1LL * ni[i] * a[i - 1] % mod;
  }
  a[0] = 0;
  return a;
}
vector<int> polyln(vector<int> a, int l) {
  return polyint(mul(polydiff(a), polyinv(a, l)));
}
vector<int> polyexp(vector<int> a, int l) {
  if (l == 1) {
    return vector<int>(1, 1);
  }
  a.resize(l);
  vector<int> b = polyexp(a, (l + 1) / 2);
  init(l << 1);
  vector<int> t = mul(b, vector<int>(1, 1) - polyln(b, l) + a);
  t.resize(l);
  return t;
}
vector<int> polypow(vector<int> a, int l, int k) {
  return polyexp(polyln(a, l) * k, l);
}
}  // namespace poly
vector<int> getans() {
  vector<int> f(0);
  for (int i = 0; i <= n + 1; i++) {
    f.push_back(ifact[i + 1]);
  }
  vector<int> ght = poly::polyinv((vector<int>(1, 1) - f) >> 1, n + 1);
  vector<int> tmp =
      poly::mul(f, poly::polyinv((vector<int>(1, 1) - f) >> 1, n + 1));
  vector<int> tw(n, 0);
  for (int i = 0; i < n; i++) {
    tw[i] = tmp[i + 1];
  }
  vector<int> h = {1, 1};
  h = poly::polyinv(poly::polyln(h, n + 3) >> 1, n + 2);
  vector<int> g = poly::polyinv((vector<int>(1, 1) - h) >> 1, n + 1);
  vector<int> ph = poly::polypow(h, n + 1, n + 1);
  vector<int> t1 = poly::mul(g, ph);
  vector<int> tmp1 = poly::mul(poly::polydiff(h), ph);
  tmp1.resize(n + 1);
  vector<int> tmp2 = poly::mul(g, g);
  tmp2.resize(n + 1);
  vector<int> t2 = poly::mul(tmp1, tmp2);
  for (int i = 0; i < n; i++) {
    tw[i] = (tw[i] + mod -
             1LL * ni[n + 1] *
                 (1LL * t1[i + 1] * (n - i + 1) % mod + t2[i + 1]) % mod) %
            mod;
  }
  for (int i = 0; i < n; i++) {
    tw[i] = 1LL * tw[i] * fact[i] % mod;
  }
  reverse(tw.begin(), tw.end());
  tmp.clear();
  for (int i = 0; i < n; i++) {
    tmp.push_back(i & 1 ? mod - ifact[i] : ifact[i]);
  }
  tw = poly::mul(tw, tmp);
  tw.resize(n);
  reverse(tw.begin(), tw.end());
  return tw;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  poly::pre();
  cin >> n;
  fact[0] = ifact[0] = 1;
  for (int i = 1; i <= n + 5; i++) {
    fact[i] = 1LL * fact[i - 1] * i % mod;
  }
  ifact[n + 5] = power(fact[n + 5], mod - 2);
  for (int i = n + 4; i >= 0; i--) {
    ifact[i] = 1LL * ifact[i + 1] * (i + 1) % mod;
  }
  for (int i = 1; i <= n + 5; i++) {
    ni[i] = 1LL * ifact[i] * fact[i - 1] % mod;
  }
  vector<int> res = getans();
  for (int i = 0; i < n; i++) {
    cout << 1LL * res[i] * fact[n] % mod * ifact[i] % mod << " ";
  }
  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;
const int mod = 998244353, g = 3, invg = (mod + 1) / 3;
int n;
const int maxn = 2e5 + 100;
int ni[maxn], fact[maxn], ifact[maxn], tw[maxn];
int power(int a, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) {
      ret = 1LL * ret * a % mod;
    }
    b /= 2;
    a = 1LL * a * a % mod;
  }
  return ret;
}
vector<int> operator+(vector<int> a, vector<int> b) {
  int t = max((int)a.size(), (int)b.size());
  vector<int> res(t);
  for (int i = 0; i < t; i++) {
    res[i] = ((i < (int)a.size() ? a[i] : 0) + (i < (int)b.size() ? b[i] : 0));
    if (res[i] >= mod) {
      res[i] -= mod;
    }
  }
  return res;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  for (int i = 0; i < (int)b.size(); i++) {
    b[i] = b[i] == 0 ? 0 : (mod - b[i]);
  }
  return a + b;
}
vector<int> operator*(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size(); i++) {
    a[i] = 1LL * a[i] * b % mod;
  }
  return a;
}
vector<int> operator>>(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size() - b; i++) {
    a[i] = a[i + b];
  }
  a.resize((int)a.size() - b);
  return a;
}
namespace poly {
int N, l;
int pre1[20][1100000], pre2[20][1100000], A[1100000], B[1100000], r[1100000];
void pre() {
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = power(g, (mod - 1) / (i << 1));
    for (int j = 0; j < i; j++) {
      pre1[r][j] = w;
      w = 1LL * w * wn % mod;
    }
  }
  for (int i = 1, r = 0; i < (1 << 19); i <<= 1, r++) {
    int w = 1, wn = power(invg, (mod - 1) / (i << 1));
    for (int j = 0; j < i; j++) {
      pre2[r][j] = w;
      w = 1LL * w * wn % mod;
    }
  }
}
void ntt(int *A, int n, int f) {
  for (int i = 0; i < n; i++) {
    if (i < r[i]) {
      swap(A[i], A[r[i]]);
    }
  }
  for (int i = 1, j = 0; i < n; i <<= 1, j++) {
    for (int l = 0; l < n; l += (i << 1)) {
      for (int k = 0; k < i; k++) {
        int x = A[l + k];
        int y = 1LL * A[l + k + i] * (f > 0 ? pre1[j][k] : pre2[j][k]) % mod;
        A[l + k] = (x + y);
        if (A[l + k] >= mod) {
          A[l + k] -= mod;
        }
        A[l + k + i] = (x - y + mod);
        while (A[l + k + i] >= mod) {
          A[l + k + i] -= mod;
        }
      }
    }
  }
  if (f < 0) {
    int inv_n = power(n, mod - 2);
    for (int i = 0; i < n; i++) {
      A[i] = 1LL * A[i] * inv_n % mod;
    }
  }
}
void init(int t) {
  N = 1, l = 0;
  while (N < t) {
    l++;
    N <<= 1;
  }
  for (int i = 0; i < N; i++) {
    r[i] = ((r[i >> 1] >> 1) | ((i & 1) ? (N >> 1) : 0));
  }
}
void getmul() {
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) {
    A[i] = 1LL * A[i] * B[i] % mod;
  }
  ntt(A, N, -1);
}
vector<int> mul(vector<int> a, vector<int> b) {
  init((int)a.size() + (int)b.size());
  for (int i = 0; i < N; i++) {
    A[i] = ((i < (int)a.size()) ? a[i] : 0);
  }
  for (int i = 0; i < N; i++) {
    B[i] = ((i < (int)b.size()) ? b[i] : 0);
  }
  getmul();
  vector<int> ret((int)a.size() + (int)b.size() - 1);
  for (int i = 0; i < (int)ret.size(); i++) {
    ret[i] = A[i];
  }
  return ret;
}
vector<int> polyinv(vector<int> a, int l) {
  if (l == 1) {
    return vector<int>(1, power(a[0], mod - 2));
  }
  a.resize(l);
  vector<int> b = polyinv(a, (l + 1) / 2);
  init(l << 1);
  for (int i = 0; i < N; i++) {
    A[i] = (i < l ? a[i] : 0);
  }
  for (int i = 0; i < N; i++) {
    B[i] = (i < (l + 1) / 2 ? b[i] : 0);
  }
  ntt(A, N, 1);
  ntt(B, N, 1);
  for (int i = 0; i < N; i++) {
    A[i] = 1LL * A[i] * B[i] % mod * B[i] % mod;
  }
  ntt(A, N, -1);
  vector<int> t = b * 2;
  t.resize(l);
  for (int i = 0; i < l; i++) {
    t[i] = (t[i] + mod - A[i]);
    if (t[i] >= mod) {
      t[i] -= mod;
    }
  }
  return t;
}
vector<int> polydiff(vector<int> a) {
  for (int i = 0; i < (int)a.size() - 1; i++) {
    a[i] = 1LL * (i + 1) * a[i + 1] % mod;
  }
  a.resize((int)a.size() - 1);
  return a;
}
vector<int> polyint(vector<int> a) {
  a.resize((int)a.size() + 1);
  for (int i = (int)a.size() - 1; i >= 1; i--) {
    a[i] = 1LL * ni[i] * a[i - 1] % mod;
  }
  a[0] = 0;
  return a;
}
vector<int> polyln(vector<int> a, int l) {
  return polyint(mul(polydiff(a), polyinv(a, l)));
}
vector<int> polyexp(vector<int> a, int l) {
  if (l == 1) {
    return vector<int>(1, 1);
  }
  a.resize(l);
  vector<int> b = polyexp(a, (l + 1) / 2);
  init(l << 1);
  vector<int> t = mul(b, vector<int>(1, 1) - polyln(b, l) + a);
  t.resize(l);
  return t;
}
vector<int> polypow(vector<int> a, int l, int k) {
  return polyexp(polyln(a, l) * k, l);
}
}  // namespace poly
vector<int> getans() {
  vector<int> f(0);
  for (int i = 0; i <= n + 1; i++) {
    f.push_back(ifact[i + 1]);
  }
  vector<int> ght = poly::polyinv((vector<int>(1, 1) - f) >> 1, n + 1);
  vector<int> tmp =
      poly::mul(f, poly::polyinv((vector<int>(1, 1) - f) >> 1, n + 1));
  vector<int> tw(n, 0);
  for (int i = 0; i < n; i++) {
    tw[i] = tmp[i + 1];
  }
  vector<int> h = {1, 1};
  h = poly::polyinv(poly::polyln(h, n + 3) >> 1, n + 2);
  vector<int> g = poly::polyinv((vector<int>(1, 1) - h) >> 1, n + 1);
  vector<int> ph = poly::polypow(h, n + 1, n + 1);
  vector<int> t1 = poly::mul(g, ph);
  vector<int> tmp1 = poly::mul(poly::polydiff(h), ph);
  tmp1.resize(n + 1);
  vector<int> tmp2 = poly::mul(g, g);
  tmp2.resize(n + 1);
  vector<int> t2 = poly::mul(tmp1, tmp2);
  for (int i = 0; i < n; i++) {
    tw[i] = (tw[i] + mod -
             1LL * ni[n + 1] *
                 (1LL * t1[i + 1] * (n - i + 1) % mod + t2[i + 1]) % mod) %
            mod;
  }
  for (int i = 0; i < n; i++) {
    tw[i] = 1LL * tw[i] * fact[i] % mod;
  }
  reverse(tw.begin(), tw.end());
  tmp.clear();
  for (int i = 0; i < n; i++) {
    tmp.push_back(i & 1 ? mod - ifact[i] : ifact[i]);
  }
  tw = poly::mul(tw, tmp);
  tw.resize(n);
  reverse(tw.begin(), tw.end());
  return tw;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  poly::pre();
  cin >> n;
  fact[0] = ifact[0] = 1;
  for (int i = 1; i <= n + 5; i++) {
    fact[i] = 1LL * fact[i - 1] * i % mod;
  }
  ifact[n + 5] = power(fact[n + 5], mod - 2);
  for (int i = n + 4; i >= 0; i--) {
    ifact[i] = 1LL * ifact[i + 1] * (i + 1) % mod;
  }
  for (int i = 1; i <= n + 5; i++) {
    ni[i] = 1LL * ifact[i] * fact[i - 1] % mod;
  }
  vector<int> res = getans();
  for (int i = 0; i < n; i++) {
    cout << 1LL * res[i] * fact[n] % mod * ifact[i] % mod << " ";
  }
  return 0;
}

```