521：最小の素因数

数 $n$ の最小の素因数を $s(n)$ と定義しよう。 $s(91)=7$ となる、なぜなら $91=7 \times 13$, そして $s(45)=3$, なぜなら $45=3 \times 3\times 5$. $2 \leq i \leq n$ の範囲における $s(i)$ の和を $S(n)$ としよう。 例えば $S(100)=1257$ である。

$S(10^{12}) \bmod 10^9$ を求めよ。