题目描述

已知函数 $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

input

4 2

output

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$

样例 2

input

2333333 2

output

514898185

样例 3

input

1234567890000 3

output

891659731

样例 4

input

66666666 10

output

32306309

样例 5

input

1000000000000000000 1000

output

933631114

样例 6

input

999999999999999989 49989

output

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$。
对于 $80\%$ 的数据， $n\leq 10^{1000000},k\leq 2000$。
对于 $100\%$ 的数据，$1\leq n\leq 10^{1000000},1\leq k\leq 50000$。