题目描述

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

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

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

数据格式与约定

输入

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

输出

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

样例

3

2

100

13045781

注释

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