3667. [CF622F] The Sum of the k-th Powers

【题目描述】

There are well-known formulas: $\displaystyle{\sum_{i = 1}^{n}{i} = {1 + 2 + \ldots + n = \frac{n(n + 1)}{2}}}$ ,

$\displaystyle{\sum_{i = 1}^{n}{i^2} = {1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}}}$ ,  $\displaystyle{\sum_{i = 1}^{n}{i^3} = {1^3 + 2^3 + \ldots + n^3 = (\textstyle{\frac{n(n+1)}{2})^2}}}$ . Also

mathematicians found similar formulas for higher degrees.

Find the value of the sum $\displaystyle{\sum_{i = 1}^{n}{i^k} = 1^k + 2^k + \ldots + n^k}$ modulo $10^9 + 7$ (So you should find the remainder after dividing the answer by the value $10^9 + 7$).

【题目翻译】

求 $\displaystyle{\sum_{i = 1}^{n}{i^k} \text{mod} (10^9 + 7)}$

【输入格式】

输入包括两个整数 $n$, $k$ ($1 \le n \le 10^9$, $0 \le k \le 10^9$)。

【输出格式】

输出一个整数 $a$，$a$ 是求和之后的值对 $10^9+7$ 求余的值

【样例输入】

4 1

【样例输出】

10

【样例说明】

$\displaystyle{\sum_{i = 1}^{4}i = 1 + 2 + 3 + 4 = 10}$

【来源】

Codeforces 622F