题目描述

给定一个正整数 $n$。

请计算满足下列条件的正整数序列 $(a_1,a_2,\ldots,a_k)$ 的数量：

1. $1 \le k$；

2. $1 \le a_1,a_2,\ldots,a_k \le n$；

3. 令

   $$d_i=\gcd(a_1,a_2,\ldots,a_i),$$

   其中 $\gcd(a_1)=a_1$。要求

   $$d_1>d_2>\cdots>d_k.$$

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

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

输入格式

输入一行一个正整数 $n$。

输出格式

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

样例

2

3

样例解释

当 $n=2$ 时，满足条件的序列共有：

(1)
(2)
(2, 1)

因此答案为 $3$。

数据范围

• $1 \le n \le 10^6$

子任务

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