AA Tree

Time limit: 0.2s Memory limit: 256MB Input: Output:

An AA tree is a binary search tree with a special structure. Every node has a value and a level. Values obey the usual binary search tree properties:

1. The value of every left child (and every node in the subtree of the left child) is less than or equal to the value of its parent.
2. The value of every right child (and every node in the subtree of the right child) is greater than or equal to the value of its parent.

Levels obey the following rules:

1. The level of every leaf node is $1$.
2. The level of every left child is exactly one less than that of its parent.
3. The level of every right child is equal to or one less than that of its parent.
4. The level of every right grandchild is strictly less than that of its grandparent.
5. Every node of level greater than one has two children.

Below are five examples of AA trees, having $3$, $5$, $5$, $11$ and $11$ nodes respectively. For clarity, right children on an equal level with their parent are shown in red.

Given two numbers $N$ and $L$, how many ways are there of arranging the values $1$, $2$, ..., $N$ in an AA tree such that it has exactly $L$ levels?

Input data

The only line of input will contain the integers $N$ and $L$ separated by a space.

Output data

Output the number of arrangements modulo $10^9 + 7$.

Constraints and clarifications

• The problem statement is slightly modified due to an error in the definition of what a binary search tree is in the original statement.
• $1 \leq L \leq 9$
• $1 \leq N \leq 10 \ 000$
# Points Constraints
0 0 Examples
1 19 $L \leq 4$
2 34 $5 \leq L \leq 7$

Example 1

stdin

5 2


stdout

2


Explanation

The two possible arrangements are shown in images $2$ and $3$ above.

Example 2

stdin

442 6


stdout

896944318


Example 3

stdin

7133 9


stdout

980381648