Пусть f_k(n) будет суммой k-тых степеней первых n натуральных чисел.

Например, f₂(10) = 1² + 2² + 3² + 4² + 5² + 6² + 7² + 8² + 9² + 10² = 385.

Пусть S_k(n) будет суммой f_k(i) для 1 ≤ i ≤ n. Например, S₄(100) = 35375333830.

Чему равна сумма S₁₀₀₀₀(10¹²) modulo p для всех простых чисел p между 2 · 10⁹ и 2 · 10⁹ + 2000?