[R51D]听取蛙声一片3 - 代码源竞赛平台

时空限制

1S/512M

题目描述

jiangly 在参加一场比赛，比赛共有 nn 道题目，题目从 11 到 nn 标号。

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

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

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

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

格式

输入格式

输入一个整数 nn。

输出格式

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

样例

样例输入 #1

6

样例输出 #1

10

样例解释 #1

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

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

样例输入 #2

354168224

样例输出 #2

15722528

数据规模

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

子任务编号 分数 n≤n\le
11 1010 2020
22 2020 350350
33 3535 10610^6
44 3535 10910^9

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