自然数幂和

给出一个n和k，求(sum_{i = 1}^n i^k)
传送门
当(n in [1, 10^6], k in [1, 10^6])时，直接快速幂求即可
当(n in[1, 10^9], k in[1, 10^6])时，用拉格朗日插值法