Задача 639
Суммирование мультипликативной функции

Мультипликативная функция $f(x)$ - это функция на множестве натуральных чисел, удовлетворяющая условиям $f(1)=1$ и $f(a b)=f(a) f(b)$ для любых двух взаимно простых натуральных чисел $a$ и $b$.

Для целого числа $k$ пусть $f_k(n)$ будет мультипликативной функцией дополнительно удовлетворяющей условию $f_k(p^e)=p^k$ для любого простого числа $p$ и любого целого числа $e>0$.
Например, $f_1(2)=2$, $f_1(4)=2$, $f_1(18)=6$ и $f_2(18)=36$.

Пусть $\displaystyle S_k(n)=\sum_{i=1}^{n} f_k(i)$. Например, $S_1(10)=41$, $S_1(100)=3512$, $S_2(100)=208090$, $S_1(10000)=35252550$ и $\displaystyle \sum_{k=1}^{3} S_k(10^{8}) \equiv 338787512 \pmod{ 1\,000\,000\,007}$.

Найдите $\displaystyle \sum_{k=1}^{50} S_k(10^{12}) \bmod 1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net