物种关系(24-4)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
小一最近对生物进化非常感兴趣,她发现不同物种之间存在亲缘关系,可以用一棵有根树来表示这些基因联系。通过研究树的形状,她想知道在限制最大基因距离的条件下,有多少种可能的进化树结构。
题目描述
小一加入了生物兴趣小组。最近她尤其喜欢研究物种之间的基因关系。比如,猴子跟猩猩有直接的亲戚关系,猩猩跟猿有直接的亲戚关系,猿和人有直接的亲戚关系,那么就有这样四个物种沿着一条链,我们可以认为人跟猴子之间的基因距离是4,因为这中间一共经历了4个物种。
现在,生物教练岐岐提出了这样一个问题:
假设有 个物种,它们构成了一棵有 个节点的有根树,其中:
(1) 节点无标号顺序,也就是所有节点都是不可区分的。
(2) 所有子树是有顺序的,也就是说,如果一个点先接了子树 ,再接了子树 ,与先接了子树 再接子树 是不同的。
(3) 这棵树上最远的基因距离不超过 ,也就是任意两个节点之间的路径上,最多包含 个点。
问:满足上述条件的不同有根有序树共有多少种?
小一觉得可以借助程序快速回答岐岐的问题。你的程序运行结果会和她的一样吗?
输入格式
第一行包含两个整数 和 。
输出格式
输出一个整数,表示满足条件的树的数量。结果需对 取模。
样例
4 4
5
样例解释 #1
当 时,树的最大深度限制不影响所有结构,总共有 5 种不同的有根有序树。

5 4
10
样例解释 #2
当 时,最多允许的基因距离为 4,一共有 10 种满足要求的树。

80 80
381008905
80 50
164540686
10 6
2750
数据范围
本题共 20 个测试点。
| 测试点编号 | 范围 | 范围 |
|---|---|---|
| 1 | =5 | |
| 2~5 | ≤15 | — |
| 6~9 | ≤70 | |
| 10~11 | ≤100 | |
| 12~13 | =n | |
| 14~15 | — | |
| 16~20 | — | |
对于所有测试数据,满足