## Sums of power sums

Published on Saturday, 1st November 2014, 10:00 pm; Solved by 518;
Difficulty rating: 40%

### Problem 487

Let fk(n) be the sum of the kth powers of the first n positive integers.

For example, f2(10) = 12 + 22 + 32 + 42 + 52 + 62 + 72 + 82 + 92 + 102 = 385.

Let Sk(n) be the sum of fk(i) for 1 ≤ in. For example, S4(100) = 35375333830.

What is  (S10000(1012) mod p) over all primes p between 2 ⋅ 109 and 2 ⋅ 109 + 2000?