Description

苏半夏 正在研究集合。

苏半夏 想要知道，对于给定的 $n$,有多少个集合 $\{ 1,2,, \dots ,n \}$ 的子集满足最大公约数为 $1$，而最小公倍数为 $n$。

但是苏半夏 并不会，请你帮帮他。因为答案可能很大，所以你只要输出这样的子集

个数对 $998244353$ 取模的结果即可。

Format

Input

第一行一个整数 $n$，其含义见题目描述部分。

Output

输出一行一个整数表示答案对 $998244353$ 取模的结果。

Samples

6

7

样例解释

所有合法的子集为 $\{1, 6\},\{2, 3\},\{1, 2, 3\},\{1, 2, 6\},\{1, 3, 6\},\{2, 3, 6\} 以及\{1, 2, 3, 6\}$。

Limitation

对于所有测试数据，$1 \leqslant n \leqslant 10^{18}$。

子任务1(30 分): $n \leqslant 20$;

子任务2(30 分): $n \leqslant 10^9$;

子任务3(20 分): $n \leqslant 10^{15}$。

子任务4(20 分): 无特殊限制。