#P18839. [Croatian CPC2020] Gospodar Gljiva

[Croatian CPC2020] Gospodar Gljiva

[Croatian CPC2020] Gospodar Gljiva

题目描述

Malnar 有无限多个蘑菇,分别用不同的非负整数 0,1,2,…0,1,2,\ldots 编号。他想挑选一些蘑菇放入袋子,满足以下条件:

  • 袋子里恰好有 nn 个蘑菇;
  • 如果编号为 x>0x>0 的蘑菇在袋子里,那么编号为 ⌊x−1k⌋\left\lfloor\dfrac{x-1}{k}\right\rfloor 的蘑菇也必须在袋子里。

其中 ⌊⋅⌋\lfloor\cdot\rfloor 表示向下取整。每个编号的蘑菇只能选择一次,选择的先后顺序不影响方案。

求不同选择方案的数量,对 109+710^9+7 取模。

输入格式

输入一行两个整数 n,kn,k(2≤n≤1062\le n\le10^6,1≤k≤1061\le k\le10^6)。

输出格式

输出一个整数,表示方案数量对 109+710^9+7 取模的结果。

样例 1

输入

3 2

输出

5

样例 2

输入

3 3

输出

12

样例 1 说明

五种方案分别为 {0,1,2}\{0,1,2\}、{0,1,3}\{0,1,3\}、{0,1,4}\{0,1,4\}、{0,2,5}\{0,2,5\} 和 {0,2,6}\{0,2,6\}。