cmmdc

Fie $N$ un număr natural. Se consideră toate tripletele de forma $(a, b, c)$, cu $1 ≤ a, b, c ≤ N$, $a \neq b \neq c \neq a$, cu proprietatea că $c$ este cel mai mare divizor comun al numerelor $a$ și $b$ ($c = \text{cmmdc}(a, b)$).

Cerință

Dându-se $N$, determinați valoarea expresiei $a_1 \cdot b_1 \cdot c_1 + a_2 \cdot b_2 \cdot c_2 + \dots + a_k \cdot b_k \cdot c_k$, unde $(a_1, b_1, c_1)$, $(a_2, b_2, c_2)$, ..., $(a_k, b_k, c_k)$ sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați restul împărțirii valorii expresiei la numărul $1\ 000\ 000\ 007$.

Date de intrare

De la tastatură se citește numărul $N$.

Date de ieșire

Pe ecran se va afișa un singur număr natural $R$ reprezentând restul împărțirii rezultatului expresiei descrise anterior la numărul $1\ 000\ 000\ 007$.

Restricții și precizări

• $3 ≤ N ≤ 10^6$

Exemplu

stdin

4

stdout

36

Explicație

Tripletele valide sunt: $(2, 3, 1)$, $(3, 4, 1)$, $(3, 2, 1)$, $(4, 3, 1)$.
$2 \cdot 3\cdot 1 + 3\cdot 4\cdot 1 +3\cdot 2\cdot 1 + 4\cdot 3\cdot 1 = 36$
Restul împărțirii numărului $36$ la $1\ 000\ 000\ 007$ este $36$.