#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

// если модуль подается на вход, убрать все <> и раскомментировать нужные строки
using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
    using M = ModInt;
    // static int MD;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    bool operator!=(const M& r) const { return v != r.v; }
    M inv() const;
    friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};

template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
    ModInt<MD> r = 1;
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }

using Mint = ModInt<998244353>;
// using Mint = double;



#define V vector
void nft(bool type, V<Mint>& a) {
    Mint G = 3;
    int n = int(a.size()), s = 0;
    while ((1 << s) < n) s++;
    assert(1 << s == n);

    static V<Mint> ep, iep;
    while (int(ep.size()) <= s) {
        ep.push_back(pow(G, Mint(-1).v / (1 << ep.size())));
        iep.push_back(ep.back().inv());
    }
    V<Mint> b(n);
    for (int i = 1; i <= s; i++) {
        int w = 1 << (s - i);
        Mint base = type ? iep[i] : ep[i], now = 1;
        for (int y = 0; y < n / 2; y += w) {
            for (int x = 0; x < w; x++) {
                auto l = a[y << 1 | x];
                auto r = now * a[y << 1 | x | w];
                b[y | x] = l + r;
                b[y | x | n >> 1] = l - r;
            }
            now *= base;
        }
        swap(a, b);
    }
}

V<Mint> multiply_nft(const V<Mint>& a, const V<Mint>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 50) {
        V<Mint> ans(n + m - 1);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) ans[i + j] += a[i] * b[j];
        return ans;
    }
    int lg = 0;
    while ((1 << lg) < n + m - 1) lg++;
    int z = 1 << lg;
    auto a2 = a, b2 = b;
    a2.resize(z);
    b2.resize(z);
    nft(false, a2);
    nft(false, b2);
    for (int i = 0; i < z; i++) a2[i] *= b2[i];
    nft(true, a2);
    a2.resize(n + m - 1);
    Mint iz = Mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
    return a2;
}

const int maxn = 1e5 + 100, inf = 1e9 + 100;

Mint fact[maxn],ifact[maxn];
Mint i2[maxn];

V<Mint> getsol(int n,const V<Mint> &C,const V<Mint> &D) {
    if(n==0) {
        if(D[0]==1) return V<Mint>({Mint(0)});
        return V<Mint>({C[0]/(Mint(1)-D[0])});
    }
    int m = n/2+1;

    auto CC = C, DD = D;
    CC.resize(m),DD.resize(m);
    auto B = getsol(m-1,CC,DD);
    auto E = multiply_nft(B, D);
    vector<Mint> Cn(n-m+1), Dn(n-m+1);
    for(int i=0;i<=n-m;i++){
        Cn[i]=i2[i+m]*E[i+m] + C[i+m];
        Dn[i] = D[i]*i2[m];
    }
    auto B2 = getsol(n-m,Cn,Dn);
    for(auto x : B2) B.push_back(x);
    return B;
}

void solve() {
    int n;
    cin >> n;
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i,ifact[i]=(fact[i]).inv();
    i2[1] = Mint(2).inv();
    for(int i=0;i<=n;i++)i2[i]=pow(i2[1], i);
    V<Mint> C(n+1), D(n+1);
    for(int i=0;i<=n;i++){
        C[i] = (Mint(1)-i2[i])*ifact[i];
        D[i] = ifact[i];
    }
    auto B = getsol(n,C,D);
    cout << B[n]*fact[n] << "\n";
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}