题目描述

给你一个整数 $n$。问：存在多少个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 满足以下条件：

• 对于任意 $1 \le i \le n-1$，均有

这里 $\operatorname{LCM}(x, y)$ 用于表示整数 $x$ 和 $y$ 的最小公倍数。

即：求有多少个长度为 $n$ 的数列，数列中任意两个相邻元素的最小公倍数都等于 $n$。

由于满足条件的数列可能很多，所以你只需要输出答案模 $10^9 + 7$ 的结果即可。

输入格式

一个整数 $n$。

输出格式

输出一个整数，表示满足条件的数列数对 $10^9 + 7$ 取模的结果。

样例

3

5

4

21

5

13

6

441

说明/提示

样例解释

当 $n = 3$ 时，满足条件的数列有：

1. $1, 3, 1$
2. $1, 3, 3$
3. $3, 1, 3$
4. $3, 3, 1$
5. $3, 3, 3$

数据规模与约定

• 对于 $10\%$ 的数据，$n \le 10$
• 对于 $20\%$ 的数据，$n \le 100$
• 对于 $30\%$ 的数据，$n \le 10^3$
• 对于 $40\%$ 的数据，$n \le 10^4$
• 对于 $100\%$ 的数据，$2 \le n \le 10^5$