#H1074. Shoot the Bullet

Shoot the Bullet

题目描述

teafrogsf 非常喜欢玩一款叫做东方文花帖[1]的游戏。在游戏中,玩家需要在躲避弹幕的同时用相机拍下弹幕,在拍下的照片数达到指定的数目时才能过关。

teafrogsf 手中只有一台需要消耗胶卷的老式相机,同时他还有 nn 种不同的胶卷。第 ii (1in1 \le i \le n) 种胶卷每一卷可以拍 ii 张照片,并且 teafrogsf 也恰好持有 ii 卷。同种胶卷之间是没有区别的。

teafrogsf 不喜欢浪费,因此如果他打算使用一卷胶卷,就必须把这卷胶卷用完。现在 teafrogsf 需要拍恰好 nn 张照片,他想知道有多少种选择胶卷的方案。

数据格式与约定

输入

输入仅包含一行一个正整数 n(1n5×105)n(1 \le n \le 5 \times 10^5),表示胶卷的种类数,同时也是 teafrogsf 需要拍的照片数。

输出

输出仅包含一行一个整数,表示方案数对 998244353998244353 取模的结果。

样例

3
2
100
13045781

注释

O(nn)\mathcal{O}(n \sqrt n) 的算法是可以通过本题的,所以请尽情使用 O(nn)\mathcal{O}(n\sqrt n) 的算法来塞满我们的评测机。当然如果你会理论复杂度更优的算法也可以测测速。


  1. 东方文花帖 - THBWiki · 专业性的东方Project维基百科 - TBSGroup (thwiki.cc) ↩︎