虽然听起来不太可能，但电话那头有个疯子声称绑架了你珍贵的孩子。你并不相信他，因为你所有的孩子（如果有的话）此刻正安然无恙地在你面前玩耍。不过，你对这种情况感到相当好奇，于是你问罪犯释放人质需要什么条件。

虽然听起来很无聊，但绑匪要的是钱。仅仅是钱。你正要失望地挂断电话时，一件奇怪的事情引起了你的注意。对方并没有告诉你他想要的具体金额。相反，他向你提出了一个谜题。

虽然听起来很荒谬，但谜题是： “存在多少个正整数构成的非空集合，使得它们的最大公约数为 1，且它们的最小公倍数为 $m$？”

接着，绑匪告诉你，这个谜题的答案对 998244353 取模后的结果，就是他想要赎回你那虚构后代所需的具体金额。

你现在很好奇绑架市场的行情，因为你已经很久没有接触这类事务了。不过，你并不打算付给绑匪一分钱。

输入格式

输入仅一行，包含一个整数 $m$ ($1 \le m \le 10^{18}$)。

输出格式

输出一个整数——绑匪向你索要的金额。

样例

样例输入 1

6

样例输出 1

7

样例输入 2

100

样例输出 2

322

说明

在第一个样例测试中，所有符合条件的集合为 $\{1, 6\}, \{2, 3\}, \{1, 2, 3\}, \{1, 2, 6\}, \{1, 3, 6\}, \{2, 3, 6\}$ 以及 $\{1, 2, 3, 6\}$。