题目描述

给定两个正整数 $n$ 与 $k$，请求出

$$\Big(1^k+2^k+\cdots+(n-1)^k+n^k\Big) \bmod {1,000,000,007}$$

输入格式

• 两个整数：表示 $n$ 与 $k$

输出格式

• 单个整数：表示答案

4 3

100

数据范围

• 对 $30\%$ 的数据，$1\leq n\leq 1,000$，$1\leq k\leq 10$
• 对 $60\%$ 的数据，$1\leq n\leq 1,000,000$，$1\leq k\leq 1,000$
• 对 $100\%$ 的数据，$1\leq n\leq 1,000,000,000$，$1\leq k\leq 1,000,000$