Magic Gems

题目来源

CF 1117D

题目描述

Reziba 拥有无限多个魔法宝石，每个魔法宝石的大小为 $1$ 单元。每个魔法宝石可以被分解为 $m$ 个普通宝石，每个普通宝石的大小也是 $1$ 单元。

现在 Reziba 需要选出一部分魔法宝石，并且选择其中一些进行分解，使得最后的宝石能够占满 $n$ 单元大小的空间。请问有多少种不同的选择与分解方案，请输出答案模 $10^9 + 7$ 。（如果两种方案选择的魔法宝石的数量不同，或者分解的魔法宝石在序列中的位置不同就认为是不同的方案）。

输入格式

第一行两个整数 $n, m$。

输出格式

一行一个数表示答案模 $10^9 + 7$ 的结果。

样例输入

4 2

样例输出

5

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^{18}, 2\leq m \leq 100$。