#6055. 「from CommonAnts」一道数学题 加强版

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

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

样例输出 1

37

样例解释 1

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

样例输出 2

514898185

样例输入 3

1234567890000 3

样例输出 3

891659731

样例输入 4

66666666 10

样例输出 4

32306309

样例输入 5

1000000000000000000 1000

样例输出 5

933631114

样例输入 6

999999999999999989 49989

样例输出 6

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