题目描述

题目译自 Romanian Master of Informatics 2023 Day1 T1 「AA Tree」

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

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

1. 每个左子节点（以及左子树中的所有节点）的值都小于等于其父节点的值。
2. 每个右子节点（以及右子树中的所有节点）的值都大于等于其父节点的值。

层级则需满足以下条件：

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

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

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

输入格式

输入只有一行，包含两个用空格分隔的整数 $N$ 和 $L$。

输出格式

输出排列方法的数量，对 $10^9 + 7$ 取模。

5 2

2

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

442 6

896944318

7133 9

980381648

数据范围与提示

对于所有输入数据，满足：

• $1 \leq L \leq 9$
• $1 \leq N \leq 10\ 000$

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

子任务	分值	附加限制
$1$	$19$	$L \leq 4$
$2$	$34$	$5 \leq L \leq 7$
$3$	$47$	无附加限制