487 : べき乗和の和

先頭から $n$ 個の正整数の $k$ 乗の和を $f_k(n)$ としよう。 例えば $f_2(10) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 = 385$ である。

$1 \leq i \leq n$ における $f_k(i)$ の和を $S_k(n)$ としよう。 例えば $S_4(100) = 35375333830$ である。

$2 \cdot 10^9$ から $2 \cdot 10^9 + 2000$ の間にある全ての素数の集合を $P$ とする。 $\displaystyle\sum_{p \in P} \big (S_{10000}(10^{12}) \bmod p \big )$ はいくつか？