题目描述

在那个植树节，晚上，小 L，小 H，小 X 讨论起了一个关于树的问题：

有多少个不同的二叉树最长链为 $N$。

但是他们发现，答案随 $N$ 增长的速度太快了，他们想不出什么好方法，便求助于你。

由于答案可能会很大，你只需要输出答案 $\mod 10^K$ 后的结果即可。

输入格式

包含两个正整数 $N,K$。表示询问有多少个不同的二叉树最长链为 $N$。

输出格式

包含一个非负整数，为答案 $\mod 10^K$ 后的结果。

样例输入

2 10

样例输出

7

提示

关于二叉树：

二叉树的递归定义：二叉树要么为空，要么由根结点，左子树，右子树组成。左子树和右子树分别是一棵二叉树。

请注意，有根树和二叉树的三个主要差别：

1. 树的结点个数至少为 $1$，而二叉树的结点个数可以为 $0$；

2. 树中结点的最大儿子个数没有限制，而二叉树结点的最大儿子个数为 $2$；

3. 树的结点无左、右之分，而二叉树的结点有左、右之分。

关于最长链：

最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径。可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点。

数据规模与约定

对于 $100\%$ 的数据，有 $N\le 2\times 10^5$，$K\le 64$。