有一些众所周知的公式: $$\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