#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int md = 998244353;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

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); roots.resize(n);
		for (int i = 1; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
		for (int mid = 1; mid < n; mid <<= 1) {
			int wn = fpow(3, (md - 1) / (mid << 1));
			roots[mid] = 1;
			for (int i = 1; i < mid; i++) roots[mid + i] = mul(roots[mid + i - 1], wn);
		}
	}
	
	void ntt(vector <int> &a, int base) {
		int n = 1 << base;
		for (int i = 1; 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) {
		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]);
		ntt(a, base); reverse(a.begin() + 1, a.end());
		int inv = fpow(1 << base, md - 2);
		for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
		a.resize(n);
		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] = add(a[i], b[i]);
		return a;
	}
}

using Poly::operator *;
using Poly::operator +;

const int N = 1e5 + 5;

vector <int> f, g;
int fac[N], inv[N], pw[N];
int n;

int main() {
	fac[0] = inv[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = fpow(fac[i], md - 2);
	}
	scanf("%d", &n);
	f.resize(n + 1); g.resize(n + 1);
	for (int i = 0; i <= n; i++) f[i] = g[i] = mul(fpow((md + 1) / 2, i), inv[i]);
	f[0] = 0; g = f * g;
	for (int base = 0; (1 << base) < n; base++) {
		vector <int> F = f, G = g;
		pw[0] = 1;
		int qwq = fpow((md + 1) / 2, 1 << base);
		for (int i = 0; i <= n; i++) {
			if (i) pw[i] = mul(pw[i - 1], qwq);
			F[i] = mul(F[i], pw[i]);
			G[i] = mul(G[i], pw[i]);
		}
		g = g + f * G;
		f = f * F;
		f.resize(n + 1); g.resize(n + 1);
	}
	printf("%d\n", mul(g[n], fac[n]));
	return 0;
}