2255. 最小生成树

【题目描述】

话说正在 jmy 愁苦如何筹钱给大家买汽水的时候，他遇上了一位魔法师。魔法师希望 jmy能帮他破解魔法书的咒语。如果 jmy 做到了，就帮他付所有买汽水的钱。

魔法书上画了一个完全图（每对不同的顶点之间有且只有一条边），每个点都有一个独一无二的 $[1,n]$ 内的编号，jmy 的任务是要找到最小生成树，以此作为魔法树，从而破解咒语。

对于完全图的边 $(i,j)(i≠j)$ 的边权恰好就等于 $i,j$ 两个数字的最大公约数。

特别地，要作为魔法树，必须满足树指定某个点为根后，所有除根以外的节点的父亲的标号必须小于自身标号。

jmy 一眼就看出了最小生成树的边权和。然而咒语却是最小生成树的个数。 为了保证大家都有汽水喝，你能帮帮 jmy 吗？

【输入格式】

一行仅一个数 N，表示完全图的大小。

【输出格式】

一行一个整数，表示答案对 100,000,007 取模（mod）的结果。

【样例输入】

3

【样例输出】

2

【提示】

【数据规模】

对于 10%的数据，N≤5；

对于 30%的数据，N≤8；

对于 40%的数据，N≤10；

对于 70%的数据，N≤5,000；

对于 100%的数据，N≤20,000。

【来源】

在此键入。