题目描述
给定一个 n−1 个点的无向图,点的编号为 2∼n。对于所有的 2≤u<v≤n,边 (u,v) 存在当且仅当 v 是 u 的正整数倍。定义 f(u,v) 表示 u 与 v 是否连通:当 u,v 连通时 f(u,v)=1,否则 f(u,v)=0。求:
(n−1∑u=2n∑v=u+1f(u,v)⋅u⋅v)mod
输入格式
从标准输入读入数据。
输入一行一个正整数 n。保证 4 \le n \le 10 ^ {11}。
输出格式
输出到标准输出。
输出一行一个非负整数表示答案。
样例
输入
4
输出
8
解释
f(u, v) = 1 当且仅当 u = 2, v = 4,故答案为 2 \times 4 = 8。
样例
输入
6
输出
80
解释
所有满足 f(u, v) = 1 的 (u, v) 为:(2, 3), (2, 4), (2, 6), (3, 4), (3, 6), (4, 6)。
样例
输入
127
输出
23573971