最小生成树
【问题描述】
话说正在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