[AdditionalFile6054.zip](file://AdditionalFile6054.zip?type=additional_file)

#6054. 「from CommonAnts」一道数学题

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

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

样例 2

输入

2333333 2

输出

514898185

样例 3

输入

1234567890000 3

输出

891659731

样例 4

输入

66666666 10

输出

32306309

样例 5

输入

1000000000000000000 1000

输出

933631114

样例 6

输入

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