Malnar 先生决定在今年举办一场新年派对，并邀请他的 $n$ 位挚友参加。由于这是年度最疯狂的夜晚，他打算送给每位朋友一颗蘑菇，让他们能将订购的玛格丽特披萨变成意式火腿蘑菇披萨。

Malnar 先生拥有无穷无尽的蘑菇，并为每一颗蘑菇都标记了一个不同的非负整数。在派对开始前，他会将蘑菇放入一个袋子中，每位客人将从中抽取一颗。不幸的是，他没能找到足够大的袋子来装下所有的蘑菇，因此他无法决定该把哪些蘑菇放入袋子。经过深思熟虑，他做出了以下决定：

• 派对开始前，袋子中必须恰好有 $n$ 颗蘑菇。
• 如果袋子中有一颗标记为 $x > 0$ 的蘑菇，那么袋子中也必须包含一颗标记为 $\lfloor \frac{x-1}{k} \rfloor$ 的蘑菇。

请帮助 Malnar 先生计算他有多少种不同的方式来准备这个装有蘑菇的袋子。

说明：由于方案数可能非常大，请输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个自然数 $n$ ($2 \le n \le 1\,000\,000$) 和 $k$ ($1 \le k \le 1\,000\,000$)。

输出格式

第一行输出方案数对 $10^9 + 7$ 取模后的结果。

样例

输入 1

3 2

输出 1

5

输入 2

3 3

输出 2

12

说明 1

对于第一个样例，可能的袋子组合为 $\{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 5\}$ 和 $\{0, 2, 6\}$。