Пусть smpf(n) будет наименьшим простым делителем числа n.
smpf(91)=7, потому что 91=7×13.
smpf(45)=3, потому что 45=3×3×5.
Пусть S(n) будет суммой smpf(i) для 2 ≤ i ≤ n.
Например, S(100)=1257.

Найдите S(10¹²) mod 10⁹.