← 返回题目列表

Codeforces · 622/F

F. k 次方之和

中文机器翻译题面 查看原题

有一些众所周知的公式: $$\sum_{i=1}^{n} i = 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$, $$\sum_{i=1}^{n} i^2 = 1^2 + 2^2 + \ldots + n^2 = \frac{n(2n+1)(n+1)}{6}$$,$$\sum_{i=1}^{n} i^3 = 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$。数学家还发现了类似的更高学位的公式。

求和 $$\sum_{i=1}^{n} i^k = 1^k + 2^k + \ldots + n^k$$ 模 109 + 7 的值(所以你应该找到答案除以值 109 + 7 后的余数)。

输入

唯一一行包含两个整数 n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106)。

输出

打印唯一的整数 a — 总和除以值 109 + 7 后的余数。

示例

输入 #1

4 1

输出 #1

10

输入 #2

4 2

输出 #2

30

输入 #3

4 3

输出 #3

100

输入#4

4 0

输出#4

4