3684: 最小生成树

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

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

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

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

jmy一眼就看出了最小生成树的边权和。然而咒语却是最小生成树的个数。

为了保证大家都有汽水喝，你能帮帮jmy吗？

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

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

3

2