B - Erase Multiples
解説
/ 
/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
整数 N が与えられます．
集合 S を S=\{1,2,\cdots,N\} で初期化します． その後，S が空になるまで次の操作を繰り返します．
- S の要素を一様ランダムに 1 つ選び，それを v とおく． S から v の倍数をすべて削除する．
操作回数の期待値を \pmod{998244353} で求めてください．
期待値 \pmod{998244353} の定義
求める期待値は必ず有理数になることが証明できます． また，この問題の制約のもとでは，その値を既約分数 \frac{P}{Q} で表した時，Q \neq 0 \pmod{998244353} となることも証明できます． よって，R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります． この R を答えてください．
制約
- 1 \leq N \leq 10^{10}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N
出力
答えを出力せよ．
入力例 1
2
出力例 1
499122178
操作回数の期待値は 3/2 です．
入力例 2
6
出力例 2
582309209
入力例 3
23
出力例 3
515759591
入力例 4
5000000000
出力例 4
64399530