定义函数 $$f_a(x) = a^x \quad (a > 0 \land a \neq 1)$$ 对于所有 $x \in (-\infty, +\infty)$。

你需要计算以下表达式的值： $$\sum_{a=2}^{n} \left( a \sum_{b=a}^{n} \lfloor f_a^{-1}(b) \rfloor \lceil f_b^{-1}(a) \rceil \right)$$

其中 $f_a^{-1}(x)$ 是 $f_a(x)$ 的反函数，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数，$\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

由于结果可能非常大，请输出该值对 $998244353$ 取模的结果。

输入格式

一个整数 $n$ ($2 \le n \le 10^{12}$)，含义如上所述。

输出格式

一个整数，表示计算出的值对 $998244353$ 取模的结果。

样例

样例输入 1

2

样例输出 1

2

样例输入 2

10

样例输出 2

236