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

typedef long long ll;
const ll mod = 998244353;
const int B = 1.5e6;
const int X = (2e10 / B);

ll F1[B + 5], F2[262150], pre[B + 5], N;
ll fpow(ll x) { return F2[x >> 18] * F1[x & 262143] % mod; }

int mu[B + 5], pr[500005], prc;
bool v[B + 5];
void precalc()
{
    F1[0] = F2[0] = 1;
    for (int i = 1; i <= B; i++) F1[i] = F1[i - 1] * 2 % mod;
    for (int i = 1; i <= (1 << 18); i++) F2[i] = F2[i - 1] * F1[1 << 18] % mod;

    v[1] = 1; mu[1] = 1;
    for (int i = 2; i <= B; i++)
    {
        if (!v[i]) pr[++prc] = i, mu[i] = -1;
        for (int j = 1; j <= prc && pr[j] <= B / i; j++)
        {
            v[i * pr[j]] = 1; mu[i * pr[j]] = mu[i] ? mod - mu[i] : 0;
            if (i % pr[j] == 0) { mu[i * pr[j]] = 0; break; }
        }
    }
    for (int i = 1; i <= B; i++)
    {
        pre[i] = pre[i - 1] + mu[i];
        if (pre[i] >= mod) pre[i] -= mod;
    }
}

ll f[B + 5], g[B + 5], h[B + 5];
void Solve()
{
    for (int d = 1; d <= B; d++)
    {
        (h[d] += f[d] + (d == 1 ? 0 : F1[d - 2])) %= mod;
        g[d] = (h[d] * 2 + f[d] * 2 + F1[d - 1]) % mod;
        for (int n = d << 1, j = 2; n <= B; n += d, j++)
        {
            (f[n] += h[d] + (F1[j / 2 - 1] - 1) * g[d]) %= mod;
            (h[n] += mu[j] * (f[d] * 3 + (d == 1 ? 1 : F1[d - 2] * 3))) %= mod;
        }
    }
    for (int i = 2; i <= B; i++) (f[i] += f[i - 1]) %= mod, (g[i] += g[i - 1]) %= mod, (h[i] += h[i - 1]) %= mod;
}

ll F[X + 10], G[X + 10], H[X + 10], S[X + 10];
inline ll qF(ll x) { return x <= B ? f[x] : F[N / x]; }
inline ll qG(ll x) { return x <= B ? g[x] : G[N / x]; }
inline ll qH(ll x) { return x <= B ? h[x] : H[N / x]; }
inline ll qS(ll x) { return x <= B ? pre[x] : S[N / x]; }
inline ll qP(ll x) { return (x & 1) ? (fpow(x / 2) - 1) * 2 % mod : (3 * fpow(x / 2 - 1) - 2) % mod; }

int main()
{
    int start = clock();
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N; precalc(); Solve();
    if (N <= B) return cout << (fpow(N - 1) + f[N]) % mod, 0;
    for (int i = (N / B); i; i--)
    {
        ll n = N / i, l = 2, r, len, d;
        S[i] = 1;
        while (l <= n)
        {
            r = n / (d = n / l), len = (r - l + 1) % mod;
            (F[i] += len * qH(d) + qG(d) * (qP(r) + 2 * mod - qP(l - 1) - len)) %= mod;
            (S[i] += (mod - len) * qS(d)) %= mod;
            l = r + 1;
        }

        l = 2; H[i] = (F[i] + fpow(n - 1) - 1) % mod;
        while (l <= n)
        {
            r = n / (d = n / l), len = qS(r) - qS(l - 1);
            if (len < 0) len += mod;
            (H[i] += len * (3 * qF(d) + 3 * fpow(d - 1) - 2)) %= mod;
            l = r + 1;
        }
        G[i] = (H[i] * 2 + F[i] * 2 + fpow(n) - 1) % mod;
    }
    cout << (fpow(N - 1) + F[1]) % mod;
	return 0;
}