#L4799. 「RMI 2023」AA Tree

「RMI 2023」AA Tree

题目描述
题目译自 Romanian Master of Informatics 20232023 Day11 T11 「AA Tree」

由于原始问题中对二叉搜索树的定义有误,本题描述略有调整。

AA 树是一种特殊的二叉搜索树,每个节点都拥有一个值和一个层级。值的排列遵循普通的二叉搜索树规则:

  • 每个左子节点(以及左子树中的所有节点)的值都小于等于其父节点的值。
  • 每个右子节点(以及右子树中的所有节点)的值都大于等于其父节点的值。

层级则需满足以下条件:

  1. 所有叶子节点的层级为 11
  2. 每个左子节点的层级比其父节点小 11
  3. 每个右子节点的层级等于或比其父节点小 11
  4. 每个右孙节点的层级必须严格小于其祖父节点的层级。
  5. 层级大于 11 的每个节点必须有两个子节点。

下面展示了五棵 AA 树的样例,分别包含 33555511111111 个节点。为了更清晰地展示,与父节点层级相同的右子节点用红色标出。

给定两个数字 N 和 L,请你计算将 1122、...、N 这 N 个值排列成一棵AA 树,且恰好有 L 个层级的方法有多少种?


输入格式
输入只有一行,包含两个用空格分隔的整数 NNLL


输出格式
输出排列方法的数量,对 109+710^9 + 7 取模。


样例 1

输入

5 2

输出

2

两种可能的排列方式如上图中的第 22 和第 33 棵树所示。


样例 2

输入

442 6

输出

896944318

样例 3

输入

7133 9

输出

980381648

数据范围与提示
对于所有输入数据,满足:

  • 1L91 \leq L \leq 9
  • 1N100001 \leq N \leq 10\,000

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
11 1919 L4L \leq 4
22 3434 5L75 \leq L \leq 7
33 4747 无附加限制