时空限制

1S/512M

题目描述

jiangly 在参加一场比赛，比赛共有 $n$ 道题目，题目从 $1$ 到 $n$ 标号。

对于每一道题，jiangly 可以选择将其 AC（通过），也可以选择将其 WA（不通过）。

这场比赛的规则很特殊：如果所有被 AC 的题目的编号的最小公倍数恰好等于 $n$，jiangly 就可以拿到大奖。

jiangly 想知道，他共有几种方案能拿到大奖？由于答案可能很大，请对 $998244353$ 取模。

注：如果没有 AC 任何题目，则其最小公倍数视为不存在（不等于 $n$）。

格式

输入格式

输入一个整数 $n$。

输出格式

输出一个整数，表示拿到大奖的方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

6

样例输出 #1

10

样例解释 #1

$n=6$ 的题目编号为 $\{1, 2, 3, 4, 5, 6\}$。只有当 AC 的题目编号集合的最小公倍数为 $6$ 时才符合要求。 符合条件的 AC 题目编号集合共有以下 $10$ 种方案：

• $\{2, 3\}$
• $\{1, 2, 3\}$
• $\{6\}$
• $\{1, 6\}$
• $\{2, 6\}$
• $\{1, 2, 6\}$
• $\{3, 6\}$
• $\{1, 3, 6\}$
• $\{2, 3, 6\}$
• $\{1, 2, 3, 6\}$

样例输入 #2

354168224

样例输出 #2

15722528

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$2 \leq n \leq 10^9$。