题目描述

已知函数 $f(k,x)(k,x\in \mathbb {N_+})$ 满足：

$$f(k,x)= \begin{cases} 1 & x=1\\ \sum_{i=1}^{x-1} f(k,i) + x^k & x>1 \end{cases}$$

现在给定 $n,k$，求 $f(k,n)$。

由于答案很大，你只需计算答案对 $10^9+7$ 取模后的值。

输入格式

一行两个十进制正整数 $n,k$。

输出格式

一行一个十进制整数，表示答案对 $10^9+7$ 取模的结果。

样例 1

4 2

37

$f(2,1)=1$

$f(2,2)=f(2,1)+2^2=5$

$f(2,3)=f(2,2)+f(2,1)+3^2=15$

$f(2,4)=f(2,3)+f(2,2)+f(2,1)+4^2=37$

2333333 2

514898185

1234567890000 3

891659731

66666666 10

32306309

1000000000000000000 1000

933631114

999999999999999989 49989

584156079

数据范围与提示

对于 $20\%$ 的数据， $n\leq 1000,k\leq 10$。
对于另外 $10\%$ 的数据， $n\leq 10^{18},k\leq 3$。
对于 $40\%$ 的数据， $n\leq 10^{18},k\leq 10$。
对于 $50\%$ 的数据， $n\leq 10^{1000000},k\leq 150$。
对于 $60\%$ 的数据， $n\leq 10^{1000000},k\leq 2000$。
对于 $80\%$ 的数据，$1\leq n\leq 10^{1000000},1\leq k\leq 50000$。
对于 $100\%$ 的数据，$1\leq n\leq 10^{1000000},1\leq k\leq 1000000$。