Description
苏半夏 正在研究集合。
苏半夏 想要知道,对于给定的 n,有多少个集合 {1,2,,…,n} 的子集满足最大公约数为 1,而最小公倍数为 n。
但是苏半夏 并不会,请你帮帮他。因为答案可能很大,所以你只要输出这样的子集
个数对 998244353 取模的结果即可。
第一行一个整数 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⩽n⩽1018。
子任务1(30 分): n⩽20;
子任务2(30 分): n⩽109;
子任务3(20 分): n⩽1015。
子任务4(20 分): 无特殊限制。