Contagem Coprima Invertida

#87
Made by: Crazynds
200MB
0.4s

Dado um número inteiro positivo $N$, defina $f(k)$ como o número de inteiros $x$ tais que:

  • $1 \leq x \leq N$
  • $\gcd(x, k) = 1$

Ou seja, $f(k)$ é o número de inteiros de $1$ a $N$ que são coprimos com $k$.

Você deve calcular a soma:

$$ S = \sum_{k=1}^{N} f(k) $$

Input

Um único inteiro $N$ $(1 \leq N \leq 5.10^6)$

Output

Um único inteiro representando o valor de $S \mod 10^9 + 7$

Input Example
Output Example 
107
7063

2
3

180
19759