Migrated from Lutece 3033 简单算数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

maco喜欢计算和式

$\sum_{i=1}^n i^k$

答案对 $10^9+7$ 取模

这是什么签到题？快速幂？

哦，原来 $n$ 的范围是 $10^9$ ，而且时限300ms，那没事了。

Input

输入两个正整数 $n$ , $k$

Output

输出答案

Samples

7 2

140

7 10

353815700

Constraints

$1≤n≤10^9$ $1≤k≤10^6$

Note

注：时限300ms是因为lutece测评机速度极快，绝对没有卡常的意思。

Resources

2023 UESTC ICPC Training for Math