题目描述

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

$$f(k, x) = \begin{cases} 1 & x = 1 \\ \displaystyle \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$
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$