Hello, I have a problem need to solve:

S(n) = 1^k + 2^k +..+n^k

input: n<=10^9, k<=40

output: S(n)%(10^9+7).

One more issue:

how to calculate ((n^k)/x)%p which very big n and k.

Thank for helping me.