#2362. 二叉树计数

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入

2 10  

样例输出

7  

数据范围与提示

对于100%的数据，有N≤200000，K≤64；

【提示】

关于二叉树：

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

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

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

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

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

关于最长链：

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