新手黑客 Vasya 梦想着成为一家大型国际 IT 公司的员工。目前，他在网上冲浪时偶然发现了一个名为 KiloBank 的银行。这个名字暗示该银行历史悠久，其安全系统可能已经过时。这正是 Vasya 所寻找的目标！经过一段时间，这位黑客获得了包含用户名和密码哈希值的数据库。现在只剩下一件小事：暴力破解原始密码并进行欺诈交易。

首先，我们当然需要弄清楚哈希函数是如何工作的。事实证明，密码长度可达数兆字节！数据库在每个用户的第一个字段中以明文形式存储了密码长度。第二个字段看起来像是密码的一个简单的 32 位哈希值。但开发人员显然明白这还不够，即使是哈希函数的大位宽迟早也无法阻止像 Vasya 这样的黑客。因此，开发人员发明了第三个字段。虽然不知道 Vasya 是如何猜出该字段含义的，但他确实做到了！他意识到，对于密码会计算一个 $\pi$ 函数，然后将其值进行哈希处理并写入数据库作为第三个字段。

给定密码 $P$ 和从 $1$ 到 $P$ 长度的位置 $i$，$\pi(i)$ 的定义如下：它是 $P$ 中从第一个字符之后开始且在第 $i$ 个字符处结束的、等于相应长度的 $P$ 的前缀的最长子串的长度。特别地，$\pi(1)$ 总是为零，因为只有空子串满足该定义。

“也许甚至可以快速计算这个函数……”，Vasya 心想，但他没有太多时间研究这个问题。现在，为了继续前进，Vasya 想了解长度为 $N$ 的字符串存在多少种不同的 $\pi$ 函数（考虑到字母表的大小没有限制：我们被允许从无限的字符集中构造字符串）。

在挖掘了公开可用的资料后，他意识到这个问题已经被研究过了。目前还没有发现寻找该数字的足够高效的算法。

然而，Vasya 思考了一会儿，认为只有少数字符串在任何位置 $i$ 处满足 $\pi(i)$ 超过 $K$，因此它们可以被完全忽略。因此，他现在想计算满足所有 $\pi(i)$ 值均不超过 $K$ 的不同 $\pi$ 函数的数量。这会简化问题吗？

Vasya 出生并成长于域 $\mathbb{Z}_{1\,000\,000\,007}$ 中，因此，他只对所求数字除以 $10^9 + 7$ 的余数感兴趣。

输入格式

输入仅一行，包含两个整数 $N$ 和 $K$ ($1 \le N \le 10\,000\,000, 0 \le K \le 10$)：字符串的长度和 Vasya 的上限。

输出格式

输出 Vasya 感兴趣的数字：长度为 $N$ 且所有 $\pi$ 函数值均不超过 $K$ 的不同 $\pi$ 函数的数量，结果对 $10^9 + 7$ 取模。

样例

输入 1

5 2

输出 1

17