#include #include #include #include #include #include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vmi = vector; using vvmi = vector; using vvvmi = vector; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) class Primes{ private: int size_p; vector is_p; vector primes; vector minfactor; vector mobius; void eratos(int n){ for(int i=2; i<=n; i++){ if(minfactor[i] < i)continue; primes.emplace_back(i); mobius[i] = -1; is_p[i] =true; for(int j = 2*i; j<=n; j+=i){ minfactor[j] = min(i, minfactor[j]); mobius[j] = ((j/i) % i == 0) ? 0 : -mobius[j]; } } } public: Primes(int n){ size_p = n; rep(i, size_p+1)is_p.emplace_back(false); rep(i, size_p+1)minfactor.emplace_back(i); rep(i, size_p+1)mobius.push_back(1); mobius[1] = 1; eratos(size_p); } bool isprime(int n){ return is_p[n]; } vector listPrimes(){ return primes; } int getMobius(int n){return mobius[n];} }; int main(){ int n; cin >> n; Primes pr(n); vi lp = pr.listPrimes(); int len = lp.size(); vll cnt(len, 0); rep(i, len){ ll p = (ll)lp[i]; for(ll j = p; j <= n; j*=p)cnt[i] += n/j; } int mx = cnt[0]; vmi cntmin(mx + 1, mint(0)); queue q; rep(i, len)q.push(cnt[i]); rep2(i, 1, mx + 1){ mint tmp = mint(1); vll del; int l = q.size(); rep(j, l){ ll u = q.front(); q.pop(); tmp *= mint(u/i) + mint(1); if(u >= i)q.push(u); } cntmin[i] = tmp - mint(1); } mint ans = mint(0); rep2(i, 1, mx) ans += mint(i)*(cntmin[i] - cntmin[i+1]); ans += mint(mx)*cntmin[mx]; cout << ans.val() << endl; return 0; }