题目描述
已知函数 f(k,x)(k,x∈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)。
由于答案很大,你只需计算答案对 109+7 取模后的值。
输入格式
一行两个十进制正整数 n,k。
输出格式
一行一个十进制整数,表示答案对 109+7 取模的结果。
4 2
37
2333333 2
514898185
1234567890000 3
891659731
66666666 10
32306309
1000000000000000000 1000
933631114
999999999999999989 49989
584156079
数据范围与提示
对于 20% 的数据, n≤1000,k≤10。
对于另外 10% 的数据, n≤1018,k≤3。
对于 40% 的数据, n≤1018,k≤10。
对于 50% 的数据, n≤101000000,k≤150。
对于 60% 的数据, n≤101000000,k≤2000。
对于 80% 的数据,1≤n≤101000000,1≤k≤50000。
对于 100% 的数据,1≤n≤101000000,1≤k≤1000000。