AA_Tree (RMI contest)
Time limit: 0.1 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: dynamic programming, combinatorics, tree dp, modular arithmetic, number theoretic transform

# AA Tree

Time limit: *100 ms*
Memory limit: *256 MB*

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 is less than or equal to the value of its parent.
2.  The value of every 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.

![Examples of AA Trees](image1.jpg)

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?

## Standard input

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

## Standard output

Output the number of arrangements modulo 1,000,000,007.

## Constraints and notes

* 1 <= L <= 9.
* 1 <= N <= 10,000.

| # | Points | Restrictions          |
|---|--------|-----------------------|
| 1 | 19     | L <= 4                |
| 2 | 34     | 5 <= L <= 7           |
| 3 | 47     | No further constraints. |

---

**Example 1:**

*Input:*
```
5 2
```
*Output:*
```
2
```

---

**Example 2:**

*Input:*
```
442 6
```
*Output:*
```
896944318
```

---

**Example 3:**

*Input:*
```
7133 9
```
*Output:*
```
980381648
```

---

### Explanations

For the first example, the two possible arrangements are shown in images 2 and 3 above.


Starter code:

Grader code:

Setup script:

Evaluation script: