该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

天道合音

题目背景

在万物初开的洪荒时代，宇宙的稳定由一种名为“天道之力”的能量维系。相传，当年的天道总值为 $n$。此力可一分为三，化为“阳”、“阴”、“和”三股气息，其力值分别为 $a$、$b$、$c$。这三股气息必须源于同宗，故其力值之和恒为天道总值 $n$。

神兽“灵羊”受天命所托，需推演宇宙和谐之道的总纲。它发现，任意一组三气息的和谐度，取决于一种玄妙的“合音”值。计算此值，需先取“阳”与“阴”二气之力 $a$ 与 $b$，求其“本源共通之力”，再将此共通之力与“和”气之力 $c$ 相融，求其“最小谐振周期”。

灵羊的任务，便是遍历所有可能的三气息组合，将其“合音”值累加，最终求得代表宇宙总和谐度的神圣数值。

题目描述

令天道总值为整数 $n$。

1. 三元气息组：一个“三元气息组”是一个有序正整数三元组 $(a, b, c)$，满足 $a, b, c \in \mathbb{Z}^+$ 且 $a + b + c = n$。

2. 本源共通之力：对于气息组中的 $a$ 和 $b$，其“本源共通之力”定义为它们的最大公约数。 $g = \gcd(a, b)$

3. 合音值：对于一个三元气息组 $(a, b, c)$，其“合音值”定义为“和”气之力 $c$ 与“本源共通之力” $g$ 的最小公倍数。 $V(a, b, c) = \operatorname{lcm}(c, g) = \operatorname{lcm}(c, \gcd(a, b))$

4. 宇宙总和谐度：此值是所有可能的三元气息组的“合音值”之和。由于结果可能极大，需对 $10^9 + 7$ 取模。

目标

给定天道总值 $n$，计算宇宙总和谐度。其数学表达式为：

输入格式

输入一个整数 $n$ ($3 \le n \le 10^5$)，代表天道总值。

输出格式

输出一个整数，代表模 $10^9 + 7$ 后的宇宙总和谐度。

样例分析

样例 #1

输入

5

输出

11

解释: 当天道总值 $n=5$ 时，存在以下 6 个三元气息组：

• $(1, 1, 3)$: $\operatorname{lcm}(3, \gcd(1,1)) = \operatorname{lcm}(3,1) = 3$
• $(1, 2, 2)$: $\operatorname{lcm}(2, \gcd(1,2)) = \operatorname{lcm}(2,1) = 2$
• $(1, 3, 1)$: $\operatorname{lcm}(1, \gcd(1,3)) = \operatorname{lcm}(1,1) = 1$
• $(2, 1, 2)$: $\operatorname{lcm}(2, \gcd(2,1)) = \operatorname{lcm}(2,1) = 2$
• $(2, 2, 1)$: $\operatorname{lcm}(1, \gcd(2,2)) = \operatorname{lcm}(1,2) = 2$
• $(3, 1, 1)$: $\operatorname{lcm}(1, \gcd(3,1)) = \operatorname{lcm}(1,1) = 1$ 宇宙总和谐度为 $3+2+1+2+2+1 = 11$。

样例 #2

输入

7

输出

42

解释: 当天道总值 $n=7$ 时，存在 15 个可能的三元气息组。将它们的合音值相加：

• 对于 $c=1$, $a+b=6$:
  • $(1,5,1)$ -> $\operatorname{lcm}(1,\gcd(1,5))=1$
  • $(2,4,1)$ -> $\operatorname{lcm}(1,\gcd(2,4))=2$
  • $(3,3,1)$ -> $\operatorname{lcm}(1,\gcd(3,3))=3$
  • (4,2,1) -> $\operatorname{lcm}(1,\gcd(4,2))=2$
  • (5,1,1) -> $\operatorname{lcm}(1,\gcd(5,1))=1$
  • 小计: $1+2+3+2+1=9$
• 对于 $c=2$, $a+b=5$:
  • (1,4,2) -> $\operatorname{lcm}(2,\gcd(1,4))=2$
  • (2,3,2) -> $\operatorname{lcm}(2,\gcd(2,3))=2$
  • (3,2,2) -> $\operatorname{lcm}(2,\gcd(3,2))=2$
  • (4,1,2) -> $\operatorname{lcm}(2,\gcd(4,1))=2$
  • 小计: $2+2+2+2=8$
• 对于 $c=3$, $a+b=4$:
  • (1,3,3) -> $\operatorname{lcm}(3,\gcd(1,3))=3$
  • (2,2,3) -> $\operatorname{lcm}(3,\gcd(2,2))=6$
  • (3,1,3) -> $\operatorname{lcm}(3,\gcd(3,1))=3$
  • 小计: $3+6+3=12$
• 对于 $c=4$, $a+b=3$:
  • (1,2,4) -> $\operatorname{lcm}(4,\gcd(1,2))=4$
  • (2,1,4) -> $\operatorname{lcm}(4,\gcd(2,1))=4$
  • 小计: $4+4=8$
• 对于 $c=5$, $a+b=2$:
  • (1,1,5) -> $\operatorname{lcm}(5,\gcd(1,1))=5$
  • 小计: $5$ 宇宙总和谐度为 $9+8+12+8+5=42$。

样例 #3

输入

57132

输出

502291108