//using ChatGPT o1-mini #include using namespace std; typedef long long ll; const int MOD = 998244353; // エラトステネスの篩で素数を列挙 vector sieve(int n){ vector is_prime(n+1, true); is_prime[0] = is_prime[1] = false; for(int i=2; i*i <=n; ++i){ if(is_prime[i]){ for(int j=i*i; j<=n; j+=i){ is_prime[j] = false; } } } vector primes; primes.reserve(80000); // 約78498個 for(int i=2; i<=n; ++i){ if(is_prime[i]) primes.push_back(i); } return primes; } // 各素数pについてN!におけるpの指数V_pを計算 vector compute_Vp(int N, const vector& primes){ vector Vp; Vp.reserve(primes.size()); for(auto p : primes){ int vp = 0; ll pp = p; while(pp <= N){ vp += N / pp; if(pp > N / p) break; // オーバーフロー防止 pp *= p; } Vp.push_back(vp); } return Vp; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; // 素数の列挙 vector primes = sieve(N); // 各素数のV_pを計算 vector Vp = compute_Vp(N, primes); // V_maxを求める int V_max = 0; for(auto vp : Vp){ V_max = max(V_max, vp); } // Vpの頻度をカウント // ここでは頻度を後でグループ化するために使用 // 同じV_pを持つ素数の数を数える // 最大 V_p は N vector freq(V_max + 2, 0); for(auto vp : Vp){ freq[vp]++; } // 素数を降順にソートしておく(V_pが高い順) sort(Vp.begin(), Vp.end(), [&](const int a, const int b) -> bool{ return a > b; }); ll S = 0; // ループをe=1からV_maxまで行う for(int e=1; e<=V_max; ++e){ ll prod = 1; // すべての素数について floor(V_p /e) +1 を掛け合わせる // ここで、V_p >= e となる素数のみ考慮 // 素数はV_pが降順にソートされているため、V_p < e になったら終了 for(auto vp : Vp){ if(vp < e){ break; } ll term = (vp / e) + 1; prod = (prod * term) % MOD; // オーバーフロー防止のため、prodが0になったら終了 if(prod == 0){ break; } } // b=1を除外するために-1 ll count_e = (prod - 1 + MOD) % MOD; S = (S + count_e) % MOD; // eが大きくなるにつれて、prodが1になる(count_e=0)ので、終了 if(prod ==1){ break; } } cout << S; }