#2362. 二叉树计数

内存限制:128 MiB 时间限制:10 Sec

题目描述

 
在那个植树节,晚上,小L,小H,小X讨论起了一个关于树的问题:
有多少个不同的二叉树最长链为N
但是他们发现,答案随N增长的速度太快了,他们想不出什么好方法,便求助于你。
由于答案可能会很大,你只需要输出答案mod 10K后的结果即可。

输入格式

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

输出格式

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

样例

样例输入


			
2 10

样例输出


			
7

数据范围与提示

对于100%的数据,有N≤200000,K≤64;

 

【提示】

关于二叉树:

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

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

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

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

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

关于最长链:

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