二叉树计数

时间限制:10s      空间限制:128MB

题目描述

 
在那个植树节,晚上,小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. 树的结点无左、右之分,而二叉树的结点有左、右之分。
关于最长链:
最长链为这棵二叉树中一条最长的简单路径,即不经过重复结点的一条路径。可以容易证明,二叉树中最长链的起始、结束结点均为叶子结点。
 



题目来源

没有写明来源