#include using namespace std; using ll = long long; using i128 = __int128_t; constexpr ll MOD = 998244353; constexpr ll INV2 = 499122177; constexpr ll INV6 = 166374059; constexpr ll INV30 = 432572553; ll mul(ll a, ll b) { return a * b % MOD; } // F(x) = Σ(i * floor(sqrt(i))) (1 <= i <= x) ll prefix(ll x) { if (x <= 0) return 0; // m = floor(sqrt(x)) ll m = sqrtl((long double)x); // 浮動小数点誤差の補正 while ((i128)(m + 1) * (m + 1) <= x) ++m; while ((i128)m * m > x) --m; ll n = m - 1; ll a = n % MOD; ll b = (n + 1) % MOD; ll c = (2 * n + 1) % MOD; // S2 = Σj^2 ll s2 = mul(mul(mul(a, b), c), INV6); // S3 = Σj^3 ll t = mul(mul(a, b), INV2); ll s3 = mul(t, t); // S4 = Σj^4 ll d = (3 * mul(a, a) % MOD + 3 * a % MOD + MOD - 1) % MOD; ll s4 = mul(mul(mul(mul(a, b), c), d), INV30); // 完全に含まれる区間 ll full = (2 * s4 + 3 * s3 + s2) % MOD; // 最後の区間 [m^2, x] ll m2 = m * m; ll tail = mul( mul(m % MOD, (m2 + x) % MOD), (x - m2 + 1) % MOD ); tail = mul(tail, INV2); return (full + tail) % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; // k >= 3 の完全累乗数をイベントとして列挙 // (a^k, a) を保存 vector> events; int max_a = 2; for (int k = 3; k <= 59; ++k) { for (ll a = 2;; ++a) { i128 p = 1; for (int j = 0; j < k && p <= N; ++j) { p *= a; } if (p > N) break; events.emplace_back((ll)p, (int)a); max_a = max(max_a, (int)a); } } sort(events.begin(), events.end()); // 逆元を前計算 vector inv(max_a + 1); inv[1] = 1; for (int i = 2; i <= max_a; ++i) { inv[i] = MOD - mul(MOD / i, inv[MOD % i]); } ll ans = 0; ll weight = 1; ll prev_sum = 0; for (size_t j = 0; j < events.size();) { ll pos = events[j].first; // 次のイベント直前までの区間和 ll next_sum = prefix(pos - 1); ll interval = (next_sum - prev_sum + MOD) % MOD; ans = (ans + mul(weight, interval)) % MOD; prev_sum = next_sum; // 同じ位置で発生するイベントをすべて処理 while (j < events.size() && events[j].first == pos) { ll a = events[j].second; // (a-1) -> a に変化 weight = mul(weight, mul(a, inv[a - 1])); ++j; } } // 最後のイベントから N まで ll tail = (prefix(N) - prev_sum + MOD) % MOD; ans = (ans + mul(weight, tail)) % MOD; cout << ans << '\n'; return 0; }