#P15616. [2023年保加利亚国家队组队赛Junior]GCD Sequences/GCD 序列

    ID: 14828 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>动态规划数论莫比乌斯反演筛法CF2100

[2023年保加利亚国家队组队赛Junior]GCD Sequences/GCD 序列

题目描述

给定一个正整数 nn。

请计算满足下列条件的正整数序列 (a1,a2,…,ak)(a_1,a_2,\ldots,a_k) 的数量:

  1. 1≤k1 \le k;

  2. 1≤a1,a2,…,ak≤n1 \le a_1,a_2,\ldots,a_k \le n;

  3. 令

    di=gcd⁡(a1,a2,…,ai),d_i=\gcd(a_1,a_2,\ldots,a_i),

    其中 gcd⁡(a1)=a1\gcd(a_1)=a_1。要求

    d1>d2>⋯>dk.d_1>d_2>\cdots>d_k.

可以证明,对于任意给定的 nn,满足条件的序列数量都是有限的。

请输出答案对 1 000 000 0071\,000\,000\,007 取模后的结果。

输入格式

输入一行一个正整数 nn。

输出格式

输出一行一个整数,表示满足条件的序列数量对 1 000 000 0071\,000\,000\,007 取模后的值。

样例

2
3

样例解释

当 n=2n=2 时,满足条件的序列共有:

(1)
(2)
(2, 1)

因此答案为 33。

数据范围

  • 1≤n≤1061 \le n \le 10^6

子任务

子任务 分值 nn
1 5 ≤5\le 5
2 10 ≤130\le 130
3 ≤4000\le 4000
4 ≤11000\le 11000
5 40 ≤400000\le 400000
6 25 ≤1000000\le 1000000

只有通过一个子任务内的全部测试,才能获得该子任务分数。